Submission #1272515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272515		yeuler	Zemljište (COCI22_zemljiste)	C++20	70 / 70	276 ms	4400 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define akeh int tc = 1; cin >> tc; while(tc--){solve();}
#define vector2d(x) vector<vector<x>>
#define pii pair<int, int>
#define pl pair<ll, ll>
#define kagamine_len ios_base::sync_with_stdio(0); cin.tie(0);
#define file_in freopen("input.txt", "r", stdin);
#define file_out freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()

using namespace std;

int main(){
    kagamine_len
    // file_in file_out

    ll r, s, a, b;
    cin >> r >> s >> a >> b;
    if (a > b) swap(a,b);

    vector2d(ll) ar(r+1, vector<ll>(s+1));
    vector2d(ll) pf(r+1, vector<ll>(s+1, 0));

    for (ll i = 1; i <= r; i++){
        for (ll j = 1; j <= s; j++){
            cin >> ar[i][j];
            pf[i][j] = ar[i][j];
            pf[i][j] += pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1];
        }
    }

    ll ans = LLONG_MAX;
    for (ll i = 1; i <= r; i++){
        for (ll j = i; j <= r; j++){
            vector<ll> kol(s+1);
            kol[0] = 0;
            for (ll k = 1; k <= s; k++){
                kol[k] = pf[j][k] - pf[i-1][k] - (pf[j][k-1] - pf[i-1][k-1]);
            }

            for (ll k = 1; k <= s; k++){
                kol[k] += kol[k-1];
            }

            ll ki = 1, ka = 1;
            while (ka <= s) {
                ll sum = kol[ka] - kol[ki-1];
                ans = min(ans, abs(sum-a) + abs(sum-b));
                while (ki <= ka && sum > b) {
                    ki++;
                    sum = kol[ka] - kol[ki-1];
                    ans = min(ans, abs(sum-a) + abs(sum-b));
                }
                ka++;
            }
        }
    }

    cout << ans;

    return 0;
}

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