Submission #1272365

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

Main

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

long long a, b;

long long jarak(long long x) {
    if (x < a) {
        return (a + b) - 2 * x;
    } else if (x > b) {
        return 2 * x - (a + b);
    } else {
        return b - a;
    }
}
int main() {
    long long r, s;
    cin >> r >> s >> a >> b;
    if (a > b) swap(a, b);
    long long grid[r + 1][s + 1];
    for (long long i = 1; i <= r; i++) {
        for (long long j = 1; j <= s; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<long long>> ps(r + 1, vector<long long>(s + 1, 0));
    for (long long i = 1; i <= r; i++) {
        for (long long j = 1; j <= s; j++) {
            ps[i][j] = ps[i - 1][j] + grid[i][j];
        }
    }
    long long ans = LLONG_MAX;
    for (long long atas = 1; atas <= r; atas++) {
        for (long long bawah = atas; bawah <= r; bawah++) {
            vector<long long> kolom(s + 1, 0);
            for (long long j = 1; j <= s; j++) {
                kolom[j] = ps[bawah][j] - ps[atas - 1][j];
            }
            multiset<long long> st;
            long long pref = 0;
            st.insert(0);
            for (long long j = 1; j <= s; j++) {
                pref += kolom[j];
                long long low = pref - b;
                auto it = st.lower_bound(low);
                if (it != st.end()) {
                    long long sub = pref - *it;
                    if (sub >= a && sub <= b) {
                        cout << (b - a) << "\n";
                        return 0;
                    }
                    ans = min(ans, jarak(sub));
                }
                if (it != st.begin()) {
                    auto it2 = it;
                    --it2;
                    long long sub = pref - *it2;
                    if (sub >= a && sub <= b) {
                        cout << (b - a) <<endl;
                        return 0;
                    }
                    ans = min(ans,jarak(sub));
                }
                st.insert(pref);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

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