답안 #51563 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51563	2018-06-18T15:49:29 Z	Flying_dragon_02	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2544 ms	63644 KB

joioi

#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;
int n,m,pos[2005];
int a[2005][2005],ans = inf,mn = inf,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++;
    }
    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(int 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];
    }
    int curMin = inf,curMax = 1,cur = m+1;
    for(int i = 1;i <= n;i++){
        cur = min(cur,pos[i]);
        curMin = min(curMin,mini[i][cur]);
        curMax = max(curMax,maxi[i][cur]);
    }
    if(curMax - curMin<=val)
        return 1;
    else
        return 0;
}

void solve(){
    int 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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	688 KB	Output is correct
4	Correct	2 ms	688 KB	Output is correct
5	Correct	2 ms	688 KB	Output is correct
6	Correct	2 ms	688 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct
8	Correct	2 ms	692 KB	Output is correct
9	Correct	2 ms	692 KB	Output is correct
10	Correct	2 ms	692 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	2 ms	748 KB	Output is correct
13	Correct	2 ms	876 KB	Output is correct
14	Correct	2 ms	876 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	688 KB	Output is correct
4	Correct	2 ms	688 KB	Output is correct
5	Correct	2 ms	688 KB	Output is correct
6	Correct	2 ms	688 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct
8	Correct	2 ms	692 KB	Output is correct
9	Correct	2 ms	692 KB	Output is correct
10	Correct	2 ms	692 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	2 ms	748 KB	Output is correct
13	Correct	2 ms	876 KB	Output is correct
14	Correct	2 ms	876 KB	Output is correct
15	Correct	5 ms	3836 KB	Output is correct
16	Correct	21 ms	4476 KB	Output is correct
17	Correct	25 ms	4492 KB	Output is correct
18	Correct	24 ms	4492 KB	Output is correct
19	Correct	25 ms	4492 KB	Output is correct
20	Correct	22 ms	4492 KB	Output is correct
21	Correct	25 ms	4492 KB	Output is correct
22	Correct	25 ms	4492 KB	Output is correct
23	Correct	24 ms	4492 KB	Output is correct
24	Correct	22 ms	4492 KB	Output is correct
25	Correct	24 ms	4492 KB	Output is correct
26	Correct	24 ms	4492 KB	Output is correct
27	Correct	25 ms	4492 KB	Output is correct
28	Correct	25 ms	4492 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	688 KB	Output is correct
4	Correct	2 ms	688 KB	Output is correct
5	Correct	2 ms	688 KB	Output is correct
6	Correct	2 ms	688 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct
8	Correct	2 ms	692 KB	Output is correct
9	Correct	2 ms	692 KB	Output is correct
10	Correct	2 ms	692 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	2 ms	748 KB	Output is correct
13	Correct	2 ms	876 KB	Output is correct
14	Correct	2 ms	876 KB	Output is correct
15	Correct	5 ms	3836 KB	Output is correct
16	Correct	21 ms	4476 KB	Output is correct
17	Correct	25 ms	4492 KB	Output is correct
18	Correct	24 ms	4492 KB	Output is correct
19	Correct	25 ms	4492 KB	Output is correct
20	Correct	22 ms	4492 KB	Output is correct
21	Correct	25 ms	4492 KB	Output is correct
22	Correct	25 ms	4492 KB	Output is correct
23	Correct	24 ms	4492 KB	Output is correct
24	Correct	22 ms	4492 KB	Output is correct
25	Correct	24 ms	4492 KB	Output is correct
26	Correct	24 ms	4492 KB	Output is correct
27	Correct	25 ms	4492 KB	Output is correct
28	Correct	25 ms	4492 KB	Output is correct
29	Correct	2272 ms	63548 KB	Output is correct
30	Correct	2135 ms	63548 KB	Output is correct
31	Correct	2330 ms	63548 KB	Output is correct
32	Correct	2299 ms	63564 KB	Output is correct
33	Correct	2092 ms	63564 KB	Output is correct
34	Correct	2506 ms	63644 KB	Output is correct
35	Correct	2544 ms	63644 KB	Output is correct
36	Correct	2071 ms	63644 KB	Output is correct
37	Correct	2357 ms	63644 KB	Output is correct

답안 #51563

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 40.0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
40.0 / 40.0