oj.uz

Submission #127204

# Submission time Handle Problem Language Result Execution time Memory
127204 2019-07-09T06:40:25 Z EntityIT The Kingdom of JOIOI (JOI17_joioi) C++14
100 / 100
 1395 ms 86384 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = (int)2e3 + 5, M = N, inf = (int)1e9 + 123;
int n, m, a[N][M], mnA = inf, mxA = -inf, sumMn[N][M], sumMx[N][M];

bool check1 () {
    for (int prv = 0, i = 1; i <= n; ++i) {
        int nxt = -1;
        for (int j = prv; j <= m; ++j) {
            if (sumMn[i][j] == j && sumMx[i][m] - sumMx[i][j] == m - j) { nxt = j; break ; }
        }
        if (nxt == -1) return false;
        prv = nxt;
    }
    return true;
}

bool check2 () {
    for (int prv = 0, i = 1; i <= n; ++i) {
        int nxt = -1;
        for (int j = prv; j <= m; ++j) {
            if (sumMx[i][j] == j && sumMn[i][m] - sumMn[i][j] == m - j) { nxt = j; break ; }
        }
        if (nxt == -1) return false;
        prv = nxt;
    }
    return true;
}

bool check3 () {
    for (int prv = m, i = 1; i <= n; ++i) {
        int nxt = -1;
        for (int j = prv; j >= 0; --j) {
            if (sumMn[i][j] == j && sumMx[i][m] - sumMx[i][j] == m - j) { nxt = j; break ; }
        }
        if (nxt == -1) return false;
        prv = nxt;
    }
    return true;
}

bool check4 () {
    for (int prv = m, i = 1; i <= n; ++i) {
        int nxt = -1;
        for (int j = prv; j >= 0; --j) {
            if (sumMx[i][j] == j && sumMn[i][m] - sumMn[i][j] == m - j) { nxt = j; break ; }
        }
        if (nxt == -1) return false;
        prv = nxt;
    }
    return true;
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            mnA = min(mnA, a[i][j]);
            mxA = max(mxA, a[i][j]);
        }
    }

    int lAns = 0, rAns = mxA - mnA;
    while (lAns < rAns) {
        int mid = (lAns + rAns) >> 1;
        memset(sumMn, 0, sizeof sumMn);
        memset(sumMx, 0, sizeof sumMx);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                sumMn[i][j] = sumMn[i][j - 1];
                sumMx[i][j] = sumMx[i][j - 1];
                if (a[i][j] - mnA <= mid) ++sumMn[i][j];
                if (mxA - a[i][j] <= mid) ++sumMx[i][j];
            }
        }
        if (check1() || check2() || check3() || check4() ) rAns = mid;
        else lAns = mid + 1;
    }

    cout << lAns;

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 31864 KB Output is correct
2 Correct 40 ms 31864 KB Output is correct
3 Correct 172 ms 31992 KB Output is correct
4 Correct 177 ms 31976 KB Output is correct
5 Correct 173 ms 31932 KB Output is correct
6 Correct 185 ms 31864 KB Output is correct
7 Correct 178 ms 32020 KB Output is correct
8 Correct 180 ms 31864 KB Output is correct
9 Correct 168 ms 31928 KB Output is correct
10 Correct 172 ms 31836 KB Output is correct
11 Correct 173 ms 31932 KB Output is correct
12 Correct 176 ms 31992 KB Output is correct
13 Correct 168 ms 31864 KB Output is correct
14 Correct 167 ms 31864 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 31864 KB Output is correct
2 Correct 40 ms 31864 KB Output is correct
3 Correct 172 ms 31992 KB Output is correct
4 Correct 177 ms 31976 KB Output is correct
5 Correct 173 ms 31932 KB Output is correct
6 Correct 185 ms 31864 KB Output is correct
7 Correct 178 ms 32020 KB Output is correct
8 Correct 180 ms 31864 KB Output is correct
9 Correct 168 ms 31928 KB Output is correct
10 Correct 172 ms 31836 KB Output is correct
11 Correct 173 ms 31932 KB Output is correct
12 Correct 176 ms 31992 KB Output is correct
13 Correct 168 ms 31864 KB Output is correct
14 Correct 167 ms 31864 KB Output is correct
15 Correct 46 ms 32076 KB Output is correct
16 Correct 43 ms 32888 KB Output is correct
17 Correct 132 ms 33080 KB Output is correct
18 Correct 125 ms 32988 KB Output is correct
19 Correct 125 ms 33016 KB Output is correct
20 Correct 122 ms 32888 KB Output is correct
21 Correct 192 ms 33400 KB Output is correct
22 Correct 183 ms 33180 KB Output is correct
23 Correct 191 ms 33188 KB Output is correct
24 Correct 190 ms 33080 KB Output is correct
25 Correct 195 ms 33272 KB Output is correct
26 Correct 182 ms 33272 KB Output is correct
27 Correct 180 ms 33272 KB Output is correct
28 Correct 184 ms 33144 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 31864 KB Output is correct
2 Correct 40 ms 31864 KB Output is correct
3 Correct 172 ms 31992 KB Output is correct
4 Correct 177 ms 31976 KB Output is correct
5 Correct 173 ms 31932 KB Output is correct
6 Correct 185 ms 31864 KB Output is correct
7 Correct 178 ms 32020 KB Output is correct
8 Correct 180 ms 31864 KB Output is correct
9 Correct 168 ms 31928 KB Output is correct
10 Correct 172 ms 31836 KB Output is correct
11 Correct 173 ms 31932 KB Output is correct
12 Correct 176 ms 31992 KB Output is correct
13 Correct 168 ms 31864 KB Output is correct
14 Correct 167 ms 31864 KB Output is correct
15 Correct 46 ms 32076 KB Output is correct
16 Correct 43 ms 32888 KB Output is correct
17 Correct 132 ms 33080 KB Output is correct
18 Correct 125 ms 32988 KB Output is correct
19 Correct 125 ms 33016 KB Output is correct
20 Correct 122 ms 32888 KB Output is correct
21 Correct 192 ms 33400 KB Output is correct
22 Correct 183 ms 33180 KB Output is correct
23 Correct 191 ms 33188 KB Output is correct
24 Correct 190 ms 33080 KB Output is correct
25 Correct 195 ms 33272 KB Output is correct
26 Correct 182 ms 33272 KB Output is correct
27 Correct 180 ms 33272 KB Output is correct
28 Correct 184 ms 33144 KB Output is correct
29 Correct 772 ms 68684 KB Output is correct
30 Correct 871 ms 69256 KB Output is correct
31 Correct 987 ms 70880 KB Output is correct
32 Correct 784 ms 70776 KB Output is correct
33 Correct 664 ms 65656 KB Output is correct
34 Correct 876 ms 70720 KB Output is correct
35 Correct 1193 ms 86384 KB Output is correct
36 Correct 1030 ms 81232 KB Output is correct
37 Correct 1395 ms 86384 KB Output is correct