prefixsum2d.cpp

#include<iostream>
#include<vector>
#include<climits>

#define long long long
#define nln '\n'

const long INF = 1e3;

using namespace std;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    //freopen("thuedat.inp", "r", stdin);
    //freopen("thuedat.out", "w", stdout);
    long m, n;
    cin >> m >> n;
    long a, b;
    cin >> b >> a;
    vector<vector<long>> mtx(n+1);
    mtx[0].resize(m+1, 0);
    for (long i = 1; i <= n; ++i){
        mtx[i].resize(m+1, 0);
        for (long j = 1; j <= m; ++j){
            cin >> mtx[i][j];
            if (mtx[i][j] == -1)
                mtx[i][j] = INF;
        }
    }

    vector<vector<long>> pfs(n+1);
    pfs[0].resize(m+1, 0);
    for (long i = 1; i <= n; ++i){
        pfs[i].resize(m+1, 0);
        for (long j = 1; j <= m; ++j)
            pfs[i][j] = pfs[i-1][j] + pfs[i][j-1] - pfs[i-1][j-1] + mtx[i][j];
    }

    long miv = LLONG_MAX;
    for (long i = 1; i <= n-a+1; ++i)
        for (long j = 1; j <= m-b+1; ++j){
            long rw1 = i, rw2 = i+a-1, cl1 = j, cl2 = j+b-1;
            long val = pfs[rw1-1][cl1-1] + pfs[rw2][cl2] - pfs[rw2][cl1-1] - pfs[rw1-1][cl2];
            if (val < miv)
                miv = val;
        }

    cout << miv << nln;

    return 0;
}