oj.uz

Submission #755197

# Submission time Handle Problem Language Result Execution time Memory
755197 2023-06-09T14:39:05 Z 1bin The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2005;
struct p{
    int x, y, d, f;
    bool operator<(const p & t)const{return d > t.d;}
};
int h, w, a[NMAX][NMAX], ans, mx, mn, L[NMAX], R[NMAX], b[NMAX][NMAX];
vector<p> v;

void rotate(){
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
            b[j][h + 1 - i] = a[i][j];
    swap(w, h);
    for(int i = 1; i <= h; i++) 
        for(int j = 1; j <= w; j++) a[i][j] = b[i][j];
    return;
}

int solve(){
    v.clear();
    memset(R, 0x3f, sizeof(R));
    memset(L, 0, sizeof(L));
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++) {
            int d = max(mx - a[i][j], a[i][j] - mn);
            int f = (d == a[i][j] - mn);
            v.push_back({j, i, d, f});
        }
    sort(all(v));

    for(auto&t : v){
        int x = t.x, y = t.y, d = t.d, f = t.f;
        if(f){
            int r = max(x, L[y]);
            for(int i = y; i <= h; i++){
                if(L[i] >= r) break;
                L[i] = r;
                if(R[i] <= r) return d;
            }
        }
        else{
            R[y] = min(R[y], x);
            if(L[y] >= R[y]) return d;
        }
    }
    return v.back().d;
}

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

    ans = mn = 2e9;
    cin >> h >> w;
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++) {
            cin >> a[i][j];
            mx = max(mx, a[i][j]);
            mn = min(mn, a[i][j]);
        }
    ans = min(mx - mn, solve());
    rotate();
    ans = min(ans, solve());
    rotate();
    ans = min(ans, solve());
    rotate();
    ans = min(ans, solve());
    cout << ans;
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -