Submission #113655

#	Time	Username	Problem	Language	Result	Execution time	Memory
113655		popovicirobert	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1805 ms	31868 KiB

joioi

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int INF = 1e9;
const int MAXN = 2000;

int mat[MAXN + 1][MAXN + 1], aux[MAXN + 1][MAXN + 1];
int n, m, mn, mx;

inline void rot() {

    int i, j;

    for(i = 1; i <= m; i++) {
        for(j = 1; j <= n; j++) {
            aux[i][j] = mat[n - j + 1][i];
        }
    }

    swap(n, m);
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            mat[i][j] = aux[i][j];
        }
    }
}


inline bool solve(int dif) {

    int l = INF, r = -INF;
    int last = 1;

    for(int j = 1; j <= m; j++) {
        int i = n;
        while(i >= max(1, last) && mat[i][j] <= mn + dif) {
            i--;
        }

        last = max(last, i + 1);

        while(i >= 1) {
            l = min(l, mat[i][j]);
            r = max(r, mat[i][j]);

            if(r - l > dif) {
                return 0;
            }

            i--;
        }
    }

    return r - l <= dif;

}


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    mx = -INF, mn = INF;

    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            cin >> mat[i][j];
            mn = min(mn, mat[i][j]);
            mx = max(mx, mat[i][j]);
        }
    }

    int ans = INF;

    for(i = 0; i < 4; i++) {

        int res = -1;
        for(int step = 1 << 29; step; step >>= 1) {
            if(res + step <= mx - mn && solve(res + step) == 0) {
                res += step;
            }
        }

        ans = min(ans, res + 1);

        if(i < 3) {
            rot();
        }

    }

    cout << ans;

    //cin.close();
    //cout.close();
    return 0;
}

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