oj.uz

Submission #518530

# Submission time Handle Problem Language Result Execution time Memory
518530 2022-01-24T03:46:47 Z Giantpizzahead The Kingdom of JOIOI (JOI17_joioi) C++17
15 / 100
 4000 ms 396 KB 
/*
Solution: 
Runtime: 
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (true) cerr
using ll = long long;

const int INF = 1e9+7;
const int MAXN = 2005;

int H, W, minV = INF, maxV = -INF;
int A[MAXN][MAXN], newA[MAXN][MAXN];

int bestAns;
void getAns(int i = 0, int j = W-1, int maxL = -INF, int minR = INF) {
    if (i == H) {
        // Check result
        bestAns = min(max(maxL - minV, maxV - minR), bestAns);
        return;
    }
    // Brute force the boundary
    for (; j >= -1; j--) {
        int newL = maxL, newR = minR;
        rep(k, 0, j+1) newL = max(A[i][k], newL);
        rep(k, j+1, W) newR = min(A[i][k], newR);
        getAns(i+1, j, newL, newR);
    }
}

void solve() {
    cin >> H >> W;
    rep(i, 0, H) rep(j, 0, W) {
        cin >> A[i][j];
        minV = min(A[i][j], minV);
        maxV = max(A[i][j], maxV);
    }

    // Try all rotations and flips
    int ans = maxV - minV;
    rep(d, 0, 8) {
        // debug << endl;
        // rep(i, 0, H) rep(j, 0, W) debug << A[i][j] << " \n"[j==W-1];
        bestAns = INF;
        getAns();
        ans = min(bestAns, ans);
        if (d != 3) {
            // Rotate board
            // (i, j) -> (j, [new W]-1-i)
            rep(i, 0, H) rep(j, 0, W) newA[j][H-1-i] = A[i][j];
            swap(H, W);
            rep(i, 0, H) rep(j, 0, W) A[i][j] = newA[i][j];
        } else {
            // Flip board
            // (i, j) -> (H-1-i, j)
            rep(i, 0, H) rep(j, 0, W) newA[H-1-i][j] = A[i][j];
            rep(i, 0, H) rep(j, 0, W) A[i][j] = newA[i][j];
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 34 ms 332 KB Output is correct
4 Correct 17 ms 396 KB Output is correct
5 Correct 39 ms 384 KB Output is correct
6 Correct 10 ms 336 KB Output is correct
7 Correct 35 ms 336 KB Output is correct
8 Correct 35 ms 352 KB Output is correct
9 Correct 36 ms 336 KB Output is correct
10 Correct 35 ms 336 KB Output is correct
11 Correct 35 ms 372 KB Output is correct
12 Correct 34 ms 336 KB Output is correct
13 Correct 35 ms 392 KB Output is correct
14 Correct 47 ms 336 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 34 ms 332 KB Output is correct
4 Correct 17 ms 396 KB Output is correct
5 Correct 39 ms 384 KB Output is correct
6 Correct 10 ms 336 KB Output is correct
7 Correct 35 ms 336 KB Output is correct
8 Correct 35 ms 352 KB Output is correct
9 Correct 36 ms 336 KB Output is correct
10 Correct 35 ms 336 KB Output is correct
11 Correct 35 ms 372 KB Output is correct
12 Correct 34 ms 336 KB Output is correct
13 Correct 35 ms 392 KB Output is correct
14 Correct 47 ms 336 KB Output is correct
15 Execution timed out 4033 ms 336 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 34 ms 332 KB Output is correct
4 Correct 17 ms 396 KB Output is correct
5 Correct 39 ms 384 KB Output is correct
6 Correct 10 ms 336 KB Output is correct
7 Correct 35 ms 336 KB Output is correct
8 Correct 35 ms 352 KB Output is correct
9 Correct 36 ms 336 KB Output is correct
10 Correct 35 ms 336 KB Output is correct
11 Correct 35 ms 372 KB Output is correct
12 Correct 34 ms 336 KB Output is correct
13 Correct 35 ms 392 KB Output is correct
14 Correct 47 ms 336 KB Output is correct
15 Execution timed out 4033 ms 336 KB Time limit exceeded
16 Halted 0 ms 0 KB -