Submission #1150846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150846		DeathIsAwe	Zemljište (COCI22_zemljiste)	C++20	70 / 70	882 ms	3384 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ll long long
ll prefix[501][501];
int grid[500][500];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a, b;
    int r, s; cin >> r >> s >> a >> b;
    if (a > b) swap(a, b);
    for (int i=0;i<r;i++) {
        for (int j=0;j<s;j++) {
            cin >> grid[i][j];
        }
    }


    for (int i=0;i<r;i++) {
        prefix[i][0] = 0;
    }
    for (int i=0;i<s;i++) {
        prefix[0][i] = 0;
    }
    for (int i=0;i<r;i++) {
        for (int j=0;j<s;j++) {
            prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
        }
    }


    ll ans = 1000000001;
    int bottom, top, middle;
    ll val1, val2;
    for (int i=0;i<r;i++) {
        for (int j=0;j<s;j++) {
            for (int k=j;k<s;k++) {
                bottom = i; top = r - 1;
                while (bottom + 1 < top) {
                    middle = (bottom + top) / 2;
                    if (prefix[middle + 1][k + 1] - prefix[middle + 1][j] - prefix[i][k + 1] + prefix[i][j] >= a) {
                        top = middle;
                    } else {
                        bottom = middle;
                    }
                }
                val1 = prefix[bottom + 1][k + 1] - prefix[bottom + 1][j] - prefix[i][k + 1] + prefix[i][j];
                val2 = prefix[top + 1][k + 1] - prefix[top + 1][j] - prefix[i][k + 1] + prefix[i][j];
                val1 = abs(a - val1) + abs(b - val1);
                val2 = abs(a - val2) + abs(b - val2);
                ans = min(ans, min(val1, val2));
            }
        }
        if (ans == abs(a - b)) {
            cout << ans; return 0;
        }
    }
    cout << ans;
}

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