WA80求教

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define N 3010
using namespace std;
typedef long long LL;
typedef long double LD;
LL Max_left[N],Max_top[N],ans,c1[N][N],c2[N][N],tot[N],a[N][N];
LL C(int x,int L,int R,int mode)
{
if (mode) return c2[x][R]-c2[x][L-1];
return c1[x][R]-c1[x][L-1];
}
void calc(int x,int y,int n,int m,int mode)
{
memset(tot,0,sizeof(tot));
int i,j;
FOR(i,1,x)
{
FOR(j,1,m-y+1)
{
tot[j]+=C(i,j,j+y-1,mode);
if (i==x)
{
if (mode) Max_left[i]=max(Max_left[i],tot[j]);
else Max_top[i]=max(Max_top[i],tot[j]);
}
}
}
FOR(i,x+1,n)
{
if (mode) Max_left[i]=Max_left[i-1];else Max_top[i]=Max_top[i-1];
FOR(j,1,m-y+1)
{
tot[j]-=C(i-x,j,j+y-1,mode);
tot[j]+=C(i,j,j+y-1,mode);
if (mode) Max_left[i]=max(Max_left[i],tot[j]);
else Max_top[i]=max(Max_top[i],tot[j]);
}
}
}
void Main(int x,int y,int n,int m)
{
memset(tot,0,sizeof(tot));
int i,j;
FOR(i,1,x)
FOR(j,1,m-y+1) tot[j]+=C(i,j,j+y-1,0);
FOR(i,x+1,n)
{
FOR(j,1,m-y+1)
{
tot[j]-=C(i-x,j,j+y-1,0);
tot[j]+=C(i,j,j+y-1,0);
int X=i-x,Y=j-1;
if (Max_top[X]+tot[j]>ans) ans=Max_top[X]+tot[j];
if (Max_left[Y]+tot[j]>ans) ans=Max_left[Y]+tot[j];
}
}
}
int main()
{
int n,m,A,B;
scanf("%d%d%d%d",&n,&m,&A,&B);
int r1=((A+B<=n&&B<=m&&A<=m)||(B<=n&&A+B<=m&&A<=n));
int r2=((2*A<=n&&B<=m)||(2*B<=n&&A<=m));
int r3=((2*A<=m&&B<=n)||(2*B<=m&&A<=n));
if (!(r1||r2||r3)) {printf("Impossible\n");return 0;}
int i,j;

FOR(i,1,n) FOR(j,1,m) scanf("%lld",&a[i][j]);
memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2));
FOR(i,1,n)
{
c1[i][0]=0;
FOR(j,1,m) c1[i][j]=c1[i][j-1]+a[i][j];
}
FOR(i,1,m)
{
c2[i][0]=0;
FOR(j,1,n) c2[i][j]=c2[i][j-1]+a[j][i];
}
FOR(i,0,N) Max_left[i]=Max_top[i]=-1e17;
calc(A,B,n,m,0);calc(B,A,n,m,0);
calc(A,B,m,n,1);calc(B,A,m,n,1);
ans=-1e17;
Main(A,B,n,m);Main(B,A,n,m);
printf("%lld\n",ans);
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1764
难度
7
分类
搜索 | 枚举 点击显示
标签
(无)
递交数
636
已通过
104
通过率
16%
被复制
3
上传者