Submission #1272527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272527		ttoopp	Zemljište (COCI22_zemljiste)	C++20	30 / 70	2095 ms	4212 KiB

Main

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    ll a, b;
    cin >> n >> m >> a >> b;

    vector<vector<ll>> A(n+1, vector<ll>(m+1, 0));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> A[i][j];
        }
    }

    // Prefix sum per kolom
    vector<vector<ll>> pref(n+1, vector<ll>(m+1, 0));
    for(int j=1; j<=m; j++){
        for(int i=1; i<=n; i++){
            pref[i][j] = pref[i-1][j] + A[i][j];
        }
    }

    auto dist = [&](ll sum){
        return llabs(a - sum) + llabs(b - sum);
    };

    ll ans = LLONG_MAX;

    // Enumerasi baris atas i, baris bawah x
    for(int i=1; i<=n; i++){
        for(int x=i; x<=n; x++){
            vector<ll> col(m+1, 0);
            for(int j=1; j<=m; j++){
                col[j] = pref[x][j] - pref[i-1][j];
            }

            // Prefix sum untuk array col
            ll curr = 0;
            set<ll> S;
            S.insert(0); // prefix awal

            for(int j=1; j<=m; j++){
                curr += col[j];

                // Kita butuh cari prefix p sehingga
                // (curr - p) dekat dengan a dan b
                for(ll target : {a, b, (a+b)/2}) {
                    ll want = curr - target;
                    auto it = S.lower_bound(want);
                    if(it != S.end()){
                        ll sumRect = curr - *it;
                        ans = min(ans, dist(sumRect));
                    }
                    if(it != S.begin()){
                        --it;
                        ll sumRect = curr - *it;
                        ans = min(ans, dist(sumRect));
                    }
                }

                S.insert(curr);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

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