oj.uz

Submission #51559

# Submission time Handle Problem Language Result Execution time Memory
51559 2018-06-18T15:39:46 Z Flying_dragon_02 The Kingdom of JOIOI (JOI17_joioi) C++14
60 / 100
 4000 ms 126308 KB 
#include<bits/stdc++.h>

using namespace std;

const long long inf = 1e9;
int n,m;
long long a[2005][2005],ans = inf,mn = inf,pos[2005],mini[2005][2005],maxi[2005][2005],temp[2005][2005];

void _rotate(){
    int numi=1,numj=1;
    for(int i = 1 ; i <= m;i++){
        for(int j = n;j >= 1;j--){
            temp[numi][numj] = a[j][i];
            numj++;
        }
        numj=1;
        numi++;
    }
    /*for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    swap(n,m);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++)
            a[i][j] = temp[i][j];
    }
}

bool check(long long val){
    for(int i = 1;i <= n;i++){
        pos[i] = m + 1;
        for(int j = 1;j <= m;j++){
            if(a[i][j] > mn + val){pos[i] = j; break;}
        }
    }
    for(int i = 1;i <= n;i++){
        mini[i][m+1] = inf;
        maxi[i][m+1] = 1;
        for(int j = m;j >= 1;j--){
            mini[i][j] = min(a[i][j],mini[i][j+1]);
            maxi[i][j] = max(a[i][j],maxi[i][j+1]);
        }
        mini[i][0] = mini[i][1]; maxi[i][0] = maxi[i][1];
    }
    long long curMin = inf,curMax = 1,cur = m;
    for(int i = 1;i <= n;i++){
        cur = min(cur,pos[i] - 1);
        curMin = min(curMin,mini[i][cur+1]);
        curMax = max(curMax,maxi[i][cur+1]);
    }
    if(curMax - curMin<=val)
        return 1;
    else
        return 0;
}

void solve(){
    long long l = 0,r = inf - 1,mid;
    while(l<r){
        mid = (l+r)/2;
        if(check(mid)) r = mid;
        else l = mid+1;
    }
    ans = min(ans,l);
}

int main(){
    cin.tie(0),ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin >> a[i][j];
            mn = min(mn,a[i][j]);
        }
    }
    solve();
    for(int i = 1;i <= 3;i++){
        _rotate();
        solve();
    }
    cout << ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 800 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 2 ms 816 KB Output is correct
10 Correct 2 ms 816 KB Output is correct
11 Correct 2 ms 816 KB Output is correct
12 Correct 3 ms 816 KB Output is correct
13 Correct 3 ms 816 KB Output is correct
14 Correct 2 ms 816 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 800 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 2 ms 816 KB Output is correct
10 Correct 2 ms 816 KB Output is correct
11 Correct 2 ms 816 KB Output is correct
12 Correct 3 ms 816 KB Output is correct
13 Correct 3 ms 816 KB Output is correct
14 Correct 2 ms 816 KB Output is correct
15 Correct 7 ms 3952 KB Output is correct
16 Correct 34 ms 5120 KB Output is correct
17 Correct 34 ms 5120 KB Output is correct
18 Correct 38 ms 5120 KB Output is correct
19 Correct 34 ms 5200 KB Output is correct
20 Correct 29 ms 5200 KB Output is correct
21 Correct 32 ms 5200 KB Output is correct
22 Correct 33 ms 5200 KB Output is correct
23 Correct 32 ms 5200 KB Output is correct
24 Correct 34 ms 5200 KB Output is correct
25 Correct 32 ms 5200 KB Output is correct
26 Correct 35 ms 5200 KB Output is correct
27 Correct 31 ms 5200 KB Output is correct
28 Correct 41 ms 5200 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 800 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 2 ms 816 KB Output is correct
10 Correct 2 ms 816 KB Output is correct
11 Correct 2 ms 816 KB Output is correct
12 Correct 3 ms 816 KB Output is correct
13 Correct 3 ms 816 KB Output is correct
14 Correct 2 ms 816 KB Output is correct
15 Correct 7 ms 3952 KB Output is correct
16 Correct 34 ms 5120 KB Output is correct
17 Correct 34 ms 5120 KB Output is correct
18 Correct 38 ms 5120 KB Output is correct
19 Correct 34 ms 5200 KB Output is correct
20 Correct 29 ms 5200 KB Output is correct
21 Correct 32 ms 5200 KB Output is correct
22 Correct 33 ms 5200 KB Output is correct
23 Correct 32 ms 5200 KB Output is correct
24 Correct 34 ms 5200 KB Output is correct
25 Correct 32 ms 5200 KB Output is correct
26 Correct 35 ms 5200 KB Output is correct
27 Correct 31 ms 5200 KB Output is correct
28 Correct 41 ms 5200 KB Output is correct
29 Correct 3685 ms 126256 KB Output is correct
30 Correct 3648 ms 126256 KB Output is correct
31 Correct 3960 ms 126308 KB Output is correct
32 Execution timed out 4009 ms 126308 KB Time limit exceeded
33 Halted 0 ms 0 KB -