# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
77835 | 2018-09-30T17:02:27 Z | Vardanyan | The Kingdom of JOIOI (JOI17_joioi) | C++14 | 1521 ms | 253164 KB |
#include <bits/stdc++.h> using namespace std; const int N = 2007; int a[N][N]; int n,m; int mns = 1000*1000*1000; bool rot(){ vector<vector<int> > v; for(int i = 1;i<=n;i++){ vector<int> u; for(int j = 1;j<=m;j++) u.push_back(a[i][j]); reverse(u.begin(),u.end()); v.push_back(u); } for(int j = 1;j<=n;j++){ for(int i = 0;i<v[j-1].size();i++){ a[i+1][j] = v[j-1][i]; } } swap(n,m); } bool check(int x){ bool f = false; int ed = m; int mx = 0; int mn = 1000*1000*1000+5; for(int i = 1;i<=n;i++){ for(int j = 1;j<=ed;j++){ if(a[i][j]-mns>x){ ed = j-1; break; } } for(int j = ed+1;j<=m;j++){ mx = max(mx,a[i][j]); mn = min(mn,a[i][j]); } } if(mx-mn<=x) f = true; return f; } int main(){ scanf("%d%d",&n,&m); for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++){ scanf("%d",&a[i][j]); mns = min(mns,a[i][j]); } int mnans = 1000*1000*1000; for(int i = 0;i<4;i++){ int l = 0; int r = 1000*1000*1000; int ans = r; while(l<=r){ int mid = (l+r)/2; if(check(mid)){ ans = mid; r = mid-1; } else l = mid+1; } mnans = min(mnans,ans); rot(); } cout<<mnans<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 508 KB | Output is correct |
3 | Correct | 2 ms | 508 KB | Output is correct |
4 | Correct | 2 ms | 576 KB | Output is correct |
5 | Correct | 2 ms | 576 KB | Output is correct |
6 | Correct | 3 ms | 576 KB | Output is correct |
7 | Correct | 2 ms | 624 KB | Output is correct |
8 | Correct | 2 ms | 672 KB | Output is correct |
9 | Correct | 2 ms | 748 KB | Output is correct |
10 | Correct | 2 ms | 748 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 | 748 KB | Output is correct |
14 | Correct | 2 ms | 748 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 508 KB | Output is correct |
3 | Correct | 2 ms | 508 KB | Output is correct |
4 | Correct | 2 ms | 576 KB | Output is correct |
5 | Correct | 2 ms | 576 KB | Output is correct |
6 | Correct | 3 ms | 576 KB | Output is correct |
7 | Correct | 2 ms | 624 KB | Output is correct |
8 | Correct | 2 ms | 672 KB | Output is correct |
9 | Correct | 2 ms | 748 KB | Output is correct |
10 | Correct | 2 ms | 748 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 | 748 KB | Output is correct |
14 | Correct | 2 ms | 748 KB | Output is correct |
15 | Correct | 3 ms | 1404 KB | Output is correct |
16 | Correct | 12 ms | 1732 KB | Output is correct |
17 | Correct | 15 ms | 1744 KB | Output is correct |
18 | Correct | 15 ms | 1856 KB | Output is correct |
19 | Correct | 17 ms | 1856 KB | Output is correct |
20 | Correct | 21 ms | 1856 KB | Output is correct |
21 | Correct | 28 ms | 1856 KB | Output is correct |
22 | Correct | 17 ms | 1856 KB | Output is correct |
23 | Correct | 26 ms | 1856 KB | Output is correct |
24 | Correct | 15 ms | 1856 KB | Output is correct |
25 | Correct | 17 ms | 1856 KB | Output is correct |
26 | Correct | 16 ms | 1856 KB | Output is correct |
27 | Correct | 16 ms | 1856 KB | Output is correct |
28 | Correct | 22 ms | 1856 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 508 KB | Output is correct |
3 | Correct | 2 ms | 508 KB | Output is correct |
4 | Correct | 2 ms | 576 KB | Output is correct |
5 | Correct | 2 ms | 576 KB | Output is correct |
6 | Correct | 3 ms | 576 KB | Output is correct |
7 | Correct | 2 ms | 624 KB | Output is correct |
8 | Correct | 2 ms | 672 KB | Output is correct |
9 | Correct | 2 ms | 748 KB | Output is correct |
10 | Correct | 2 ms | 748 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 | 748 KB | Output is correct |
14 | Correct | 2 ms | 748 KB | Output is correct |
15 | Correct | 3 ms | 1404 KB | Output is correct |
16 | Correct | 12 ms | 1732 KB | Output is correct |
17 | Correct | 15 ms | 1744 KB | Output is correct |
18 | Correct | 15 ms | 1856 KB | Output is correct |
19 | Correct | 17 ms | 1856 KB | Output is correct |
20 | Correct | 21 ms | 1856 KB | Output is correct |
21 | Correct | 28 ms | 1856 KB | Output is correct |
22 | Correct | 17 ms | 1856 KB | Output is correct |
23 | Correct | 26 ms | 1856 KB | Output is correct |
24 | Correct | 15 ms | 1856 KB | Output is correct |
25 | Correct | 17 ms | 1856 KB | Output is correct |
26 | Correct | 16 ms | 1856 KB | Output is correct |
27 | Correct | 16 ms | 1856 KB | Output is correct |
28 | Correct | 22 ms | 1856 KB | Output is correct |
29 | Correct | 1258 ms | 31500 KB | Output is correct |
30 | Correct | 1152 ms | 52748 KB | Output is correct |
31 | Correct | 1223 ms | 76760 KB | Output is correct |
32 | Correct | 1242 ms | 99948 KB | Output is correct |
33 | Correct | 1073 ms | 117972 KB | Output is correct |
34 | Correct | 1234 ms | 143400 KB | Output is correct |
35 | Correct | 1466 ms | 182132 KB | Output is correct |
36 | Correct | 1318 ms | 213800 KB | Output is correct |
37 | Correct | 1521 ms | 253164 KB | Output is correct |