1 条题解

  • 0
    @ 2025-9-10 8:54:40

    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
    上传者