답안 #89853 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89853	2018-12-18T15:30:00 Z	Dat160601	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	2268 ms	263168 KB

joioi

#include <bits/stdc++.h>
using namespace std;

int n, m, mini = 2e9, maxi = 0, a[2007][2007], sv[2007][2007];

bool Check(int x, int n, int m){
	int cur = m, mi = 2e9, mx = 0;
	bool ok = true;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= cur; j++){
			if(sv[i][j] - mini > x){
				cur = j - 1;
				break;
			}
		}
		for(int j = cur + 1; j <= m; j++){
			mi = min(mi, sv[i][j]), mx = max(mx, sv[i][j]);
		}
		if(mx - mi > x){
			ok = false;
			break;
		}
	}
	if(ok) return true;
	cur = 1, mi = 2e9, mx = 0;
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= cur; j--){
			if(sv[i][j] - mini > x){
				cur = j + 1;
				break;
			}
		}
		for(int j = cur - 1; j >= 1; j--){
			mi = min(mi, sv[i][j]), mx = max(mx, sv[i][j]);
		}
		if(mx - mi > x) return false;
	}
	return true;
}

bool check(int x){
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[i][j] = a[i][j];
	if(Check(x, n, m)) return true;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[i][j] = a[n - i + 1][j];
	if(Check(x, n, m)) return true;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[j][i] = a[i][j];
	if(Check(x, m, n)) return true;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[j][i] = a[i][m - j + 1];
	if(Check(x, m, n)) return true;
	return false;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			mini = min(mini, a[i][j]);
			maxi = max(maxi, a[i][j]);
		}
	}
	int l = 0, r = maxi, mid = (l + r) / 2;
	while(l < r){
		if(check(mid)) r = mid;
		else l = mid + 1;
		mid = (l + r) / 2;
	}
	cout << mid;
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	628 KB	Output is correct
3	Correct	2 ms	628 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	660 KB	Output is correct
14	Correct	2 ms	744 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	628 KB	Output is correct
3	Correct	2 ms	628 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	660 KB	Output is correct
14	Correct	2 ms	744 KB	Output is correct
15	Correct	3 ms	1432 KB	Output is correct
16	Correct	9 ms	2720 KB	Output is correct
17	Correct	14 ms	2988 KB	Output is correct
18	Correct	15 ms	3276 KB	Output is correct
19	Correct	13 ms	3560 KB	Output is correct
20	Correct	10 ms	3708 KB	Output is correct
21	Correct	16 ms	4200 KB	Output is correct
22	Correct	15 ms	4604 KB	Output is correct
23	Correct	15 ms	4960 KB	Output is correct
24	Correct	13 ms	5252 KB	Output is correct
25	Correct	15 ms	5752 KB	Output is correct
26	Correct	16 ms	6140 KB	Output is correct
27	Correct	16 ms	6552 KB	Output is correct
28	Correct	23 ms	6916 KB	Output is correct

Subtask #3
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	628 KB	Output is correct
3	Correct	2 ms	628 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	628 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	660 KB	Output is correct
14	Correct	2 ms	744 KB	Output is correct
15	Correct	3 ms	1432 KB	Output is correct
16	Correct	9 ms	2720 KB	Output is correct
17	Correct	14 ms	2988 KB	Output is correct
18	Correct	15 ms	3276 KB	Output is correct
19	Correct	13 ms	3560 KB	Output is correct
20	Correct	10 ms	3708 KB	Output is correct
21	Correct	16 ms	4200 KB	Output is correct
22	Correct	15 ms	4604 KB	Output is correct
23	Correct	15 ms	4960 KB	Output is correct
24	Correct	13 ms	5252 KB	Output is correct
25	Correct	15 ms	5752 KB	Output is correct
26	Correct	16 ms	6140 KB	Output is correct
27	Correct	16 ms	6552 KB	Output is correct
28	Correct	23 ms	6916 KB	Output is correct
29	Correct	1150 ms	57952 KB	Output is correct
30	Correct	1455 ms	80152 KB	Output is correct
31	Correct	1362 ms	103400 KB	Output is correct
32	Correct	1383 ms	126416 KB	Output is correct
33	Correct	1349 ms	144356 KB	Output is correct
34	Correct	1403 ms	169744 KB	Output is correct
35	Correct	2268 ms	207896 KB	Output is correct
36	Correct	1591 ms	238688 KB	Output is correct
37	Runtime error	2149 ms	263168 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.

답안 #89853

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
0 / 40.0