Submission #1036128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036128		vjudge1	Zemljište (COCI22_zemljiste)	C++17	70 / 70	790 ms	4952 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 505;
int n, m, a, b, i, j, x, y;
ll mat[N][N], sm, tmp, ans;

ll f(int y){
    return mat[x][y] - mat[x][j - 1] - mat[i - 1][y] + mat[i - 1][j - 1];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> a >> b;
    for (i = 1; i <= n; i ++){
        for (j = 1; j <= m; j ++){
            cin >> mat[i][j];

            mat[i][j] += mat[i - 1][j];
            mat[i][j] += mat[i][j - 1];
            mat[i][j] -= mat[i - 1][j - 1];
        }
    }

    if (b < a) swap(a, b);

    ans = 1e18;
    for (i = 1; i <= n; i ++){
        for (j = 1; j <= m; j ++){
            y = m;
            for (x = i; x <= n; x ++){
                while (y - 1 >= j and f(y) > b){
                    sm = f(y);
                    tmp = abs(a - sm) + abs(b - sm);
                    ans = min(ans, tmp);
                    y--;
                }

                sm = f(y);
                tmp = abs(a - sm) + abs(b - sm);
                ans = min(ans, tmp);

                if (y + 1 <= m) sm = f(y + 1);
                tmp = abs(a - sm) + abs(b - sm);
                ans = min(ans, tmp);
            }
        }
    }

    cout << ans << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40