Submission #1180843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180843		patgra	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	1125 ms	32112 KiB

joioi

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n, vector<int>(m));
    rep(i, 0, n) rep(j, 0, m) cin >> arr[i][j];
    int ans = 2e9;
    int maxAll = 0;
    rep(i, 0, n) rep(j, 0, m) maxAll = max(maxAll, arr[i][j]);
    rep(_, 0, 4) {
        DEBUG {
            rep(i, 0, n) { rep(j, 0, m) DC << arr[i][j] << ' '; DC << eol; }
            DC << eol;
        }
        int l = -1, e, r = maxAll;
        while(r - l > 1) {
            e = (l + r) / 2;
            DC << "e = " << e << eol;
            vector<int> maxv(n, 1e9);
            rep(i, 0, n) rep(j, 0, m) if(maxAll - arr[i][j] > e) maxv[i] = min(maxv[i], j);
            int start = m;
            int maxH = 0, minH = 1e9;
            rep(i, 0, n) {
                start = min(start, maxv[i]);
                DC << ' ' << start << eol;
                rep(j, start, m) maxH = max(maxH, arr[i][j]), minH = min(minH, arr[i][j]);
            }
            DC << "  " << minH << ' ' << maxH << eol;
            if(maxH - minH <= e) r = e;
            else l = e;
        }
        ans = min(ans, r);
        vector<vector<int>> tmp(m, vector<int>(n));
        rep(i, 0, n) rep(j, 0, m) tmp[j][n - i - 1] = arr[i][j];
        swap(arr, tmp);
        swap(n, m);
    }
    cout << ans << eol;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40