Submission #1272728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272728		ezrapo	Zemljište (COCI22_zemljiste)	C++20	70 / 70	258 ms	4396 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // input
    int r, s, a, b; cin >> r >> s >> a >> b;
    int L=min(a, b), R=max(a, b);
    vector<vector<int>> grid(r+1, vector<int>(s+1, 0));
    for (int i=1; i<=r; i++) {
        for (int j=1; j<=s; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<int>> pref_row(r+1, vector<int>(s+1, 0));
    for (int i=1; i<=r; i++) {
        for (int j=1; j<=s; j++) {
            pref_row[i][j]=grid[i][j]+pref_row[i][j-1];
        }
    }
    auto calcdist=[&](int x) {
        if (x<L) return L-x;
        if (x>R) return x-R;
        return 0LL;
    };
    int bestdist=LLONG_MAX;
    for (int left=1; left<=s; left++) {
        for (int right=left; right<=s; right++) {
            vector<int> rowsum(r+1);
            for (int k=1; k<=r; k++) rowsum[k]=pref_row[k][right]-pref_row[k][left-1];
            int top=1, bot=1;
            int cur=0;
            while (top<=r) {
                while (bot<=r && cur<L) {
                    cur+=rowsum[bot];
                    bot++;
                }
                if (bot>top) {
                    if (L<=cur && cur<=R) {cout << R-L; return 0;}
                    else {
                        bestdist=min({bestdist, calcdist(cur), calcdist(cur-rowsum[bot-1])});
                    }
                }
                cur-=rowsum[top];
                top++;
                if (bot<top) bot=top, cur=0;
            }

        }
    }
    cout << (R-L)+2*bestdist;
}

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