Submission #1272514

#TimeUsernameProblemLanguageResultExecution timeMemory
1272514yeulerZemljište (COCI22_zemljiste)C++20
0 / 70
1 ms576 KiB
#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 (kol[ka]-kol[ki-1] > b){
                    ki++;
                }
                sum = kol[ka]-kol[ki-1];
                ans = min(ans, abs(sum-a)+abs(sum-b));
                ka++;
            }
        }
    }

    cout << ans;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...