oj.uz

Submission #50317

# Submission time Handle Problem Language Result Execution time Memory
50317 2018-06-10T05:42:16 Z 노영훈(#1281, Diuven) The Kingdom of JOIOI (JOI17_joioi) C++11
0 / 100
 2 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long lld;
const int MX=2010, inf=2e9;

int B[MX][MX];
int w, h;
vector<int> X;

int solve(){
    multiset<int> J;
    for(int i=1; i<=h; i++)
        for(int j=1; j<=w; j++)
            J.insert(B[i][j]);
    int pos[MX]={}; pos[0]=w;
    int mn=inf, mx=0, ans=inf;
    for(int x:X){
        for(int i=1; i<=h; i++){
            while(pos[i]<pos[i-1] && B[i][pos[i]+1]<=x){
                int now=B[i][pos[i]+1];
                pos[i]++;
                mn=min(mn, now); mx=max(mx, now);
                J.erase(J.find(now));
            }
        }
        if((int)J.size()==w*h || J.empty()) continue;
        ans=min(ans, max(mx-mn, *J.rbegin()-*J.begin()));
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>h>>w;
    for(int i=1; i<=h; i++)
        for(int j=1; j<=w; j++)
            cin>>B[i][j], X.push_back(B[i][j]);
    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end())-X.begin());
    int ans=solve();
    for(int i=1; i<=h; i++)
        reverse(B[i]+1, B[i]+w+1);
    ans=min(ans, solve());
    for(int j=1; j<=w; j++)
        for(int i=1; i<=h/2; i++)
            swap(B[i][j], B[h-i][j]);
    ans=min(ans, solve());
    for(int i=1; i<=h; i++)
        reverse(B[i]+1, B[i]+w+1);
    ans=min(ans, solve());
    cout<<ans;
    return 0;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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