带限制条件的最大子矩阵 - 牛客

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 1e6+5;
typedef pair<ll, ll>pa;

ll n, m;
ll x, y, z;
ll mp[505][505], sum[505][505], cnt[505][505], ze[505][505];
ll f[505], f2[505];
pa que[2005];

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> m >> x >> y >> z;
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            scanf("%lld", &mp[i][j]);
            if (mp[i][j] == 0) ze[i][j] = 1;
        }
    }    
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            cnt[i][j] = cnt[i-1][j]+ze[i][j];
            sum[i][j] = sum[i-1][j]+mp[i][j];
        }
    } 

    ll ans = 0;
    for(ll i = 1; i <= n; i++){
        for(ll j = i; j <= n; j++){
            if (j-i+1 > x) break;
            ll l=0, r = 0 ;
            memset(que, 0, sizeof(que));
            memset(f, 0, sizeof(f));
            memset(f2, 0, sizeof(f2));
            for(ll k = 1; k <= m; k++){
                ll num = sum[j][k]-sum[i-1][k];
                ll zero = cnt[j][k]-cnt[i-1][k];
                f[k] = f[k-1]+num;                
                f2[k] = f2[k-1]+zero;

                while (l < r && que[r-1].first > f[k]){
                    r--;
                }
                que[r++] = make_pair(f[k], k);
                
                while(l < r && k-que[l].second+1 > y) {l++; }
                while(l < r && f2[k]-f2[que[l].second-1] > z) {l++; }
                if (l< r) ans = max(ans, f[k]-f[que[l].second-1]);
                
                //prllf("%lld %lld %lld %lld  l = %lld r = %lld \n", i, j, k, ans, l, r);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}