제출 #1272299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272299		Popo	Zemljište (COCI22_zemljiste)	C++20	30 / 70	2096 ms	1616 KiB

Main

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

ll solve(const vector<vector<int>>& g, int R, int C, ll lo, ll hi) {
    ll best = LLONG_MAX;

    for (int top = 0; top < R; ++top) {
        vector<ll> v(C, 0);
        for (int bot = top; bot < R; ++bot) {
            for (int j = 0; j < C; ++j) v[j] += g[bot][j];
            multiset<ll> s;
            ll pref = 0;
            s.insert(0);

            for (int j = 0; j < C; ++j) {
                pref += v[j];

                auto chk = [&](ll T) {
                    ll key = pref - T;
                    auto it = s.lower_bound(key);
                    if (it != s.end()) {
                        ll sum = pref - *it;
                        ll d = 0;
                        if (sum < lo) d = lo - sum;
                        else if (sum > hi) d = sum - hi;
                        best = min(best, d);
                    }
                    if (it != s.begin()) {
                        --it;
                        ll sum = pref - *it;
                        ll d = 0;
                        if (sum < lo) d = lo - sum;
                        else if (sum > hi) d = sum - hi;
                        best = min(best, d);
                    }
                };

                chk(lo);
                if (best == 0) return 0;
                chk(hi);
                if (best == 0) return 0;

                s.insert(pref);
            }
        }
    }
    return best;
}

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

    int r, c; ll a, b;
    cin >> r >> c >> a >> b;
    vector<vector<int>> g(r, vector<int>(c));
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            cin >> g[i][j];

    ll lo = min(a, b), hi = max(a, b);

    ll ans;
    if (r <= c) {
        ans = solve(g, r, c, lo, hi);
    } else {
        vector<vector<int>> tr(c, vector<int>(r));
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                tr[j][i] = g[i][j];
        ans = solve(tr, c, r, lo, hi);
    }

    cout << (hi - lo) + 2 * ans << endl;
    return 0;
}

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