1 条题解
-
0
C++ :
#define MAXN 1010UL #define lson l,mid,t #define rson mid+1,r,t|1 #include <cstdio> int n,m,m4,A,B,C,D,s[MAXN][MAXN],ml,mr,Ans,posl,posr; inline int MIN(int a,int b){ return a<b?a:b; } inline int in(){ int x=0,c=getchar(); while(c<'0'||c>'9') c=getchar(); for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-48; return x; } inline int Martix(int x,int y){ if(x<C||y<D) return 0x1fffffff; return s[x][y]-s[x-C][y]-s[x][y-D]+s[x-C][y-D]; } inline int Martix_Biger(int x,int y){ return s[x][y]-s[x-A][y]-s[x][y-B]+s[x-A][y-B]; } struct SegTree{ int id,tr[MAXN<<2],pl,pr; inline void s_Build(int l,int r,int rt){ if(l==r){tr[rt]=Martix(id,l);return;} int mid=(l+r)>>1,t=rt<<1; s_Build(lson);s_Build(rson); tr[rt]=MIN(tr[t],tr[t|1]); return; } inline int s_QUERY(int l,int r){ pl=l,pr=r;return s_Query(1,m,1); } inline int s_Query(int l,int r,int rt){ if(pl<=l&&pr>=r) return tr[rt]; int mid=(l+r)>>1,t=rt<<1,rtn=0x2fffffff; if(pl<=mid) rtn=s_Query(lson); if(pr>mid){ int temp=s_Query(rson); if(temp<rtn) rtn=temp; } return rtn; } friend SegTree operator + (const SegTree a,const SegTree b){ SegTree c; for(int i=1;i<=m4;i++) c.tr[i]=MIN(a.tr[i],b.tr[i]); return c; } }tree[MAXN<<2]; inline void Build(int l,int r,int rt){ if(l==r){ tree[rt].id=l; tree[rt].s_Build(1,m,1); return; } int mid=(l+r)>>1,t=rt<<1; Build(lson);Build(rson); tree[rt]=tree[t]+tree[t|1]; return; } inline int Query(int l,int r,int rt){ if(posl<=l&&posr>=r){ return tree[rt].s_QUERY(ml,mr); } int mid=(l+r)>>1,t=rt<<1,rtn=0x2fffffff; if(posl<=mid) rtn=Query(lson); if(posr>mid){ int temp=Query(rson); if(temp<rtn) rtn=temp; } return rtn; } int main(){ scanf("%d%d%d%d%d%d",&n,&m,&A,&B,&C,&D);m4=m*3; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s[i][j]=in(),s[i][j]+=s[i][j-1]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s[i][j]+=s[i-1][j]; Build(1,n,1); for(int i=A;i<=n;i++){ posl=i-A+1+C;posr=i-1; for(int j=B;j<=m;j++){ ml=j-B+1+D;mr=j-1; int p=Martix_Biger(i,j)-Query(1,n,1); if(p>Ans) Ans=p; } } printf("%d\n",Ans); return 0; }
- 1
信息
- ID
- 3343
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者