답안 #61130 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61130	2018-07-25T08:31:13 Z	gusfring	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2764 ms	59212 KB

joioi

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5005;
 
int n, m, mn = 1e9, a[N][N], b[N][N], f[N];
 
bool check0(int x) {
	f[0] = 1e9;
	int _mn, _mx;
	_mn = 1e9, _mx = 0;
	for (int i = 1; i <= n; ++i) {
		int mx = 0; f[i] = 0;
		for (int j = 1; j <= m; ++j) {
			mx = max(mx, b[i][j]);
			if (mx - mn > x) break;
			f[i]++;
		}
		f[i] = min(f[i], f[i - 1]);
		for (int j = f[i] + 1; j <= m; ++j) {
			_mn = min(_mn, b[i][j]);
			_mx = max(_mx, b[i][j]);
		}
	}
	return _mx - _mn <= x;
}
 
bool check1(int x) {
	bool ok = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			b[i][j] = a[i][j];
		}
	}
	ok |= check0(x);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			b[i][j] = a[i][m - j + 1];
		}
	}
	ok |= check0(x);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			b[i][j] = a[n - i + 1][j];
		}
	}
	ok |= check0(x);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			b[i][j] = a[n - i + 1][m - j + 1];
		}
	}
	ok |= check0(x);
	return ok;
}
 
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]); mn = min(mn, a[i][j]);
		}
	}
 
	int l = 0, r = 1e9;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check1(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l;
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp:61:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]); mn = min(mn, a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	3 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	3 ms	644 KB	Output is correct
6	Correct	2 ms	644 KB	Output is correct
7	Correct	2 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	3 ms	644 KB	Output is correct
10	Correct	2 ms	644 KB	Output is correct
11	Correct	3 ms	644 KB	Output is correct
12	Correct	2 ms	644 KB	Output is correct
13	Correct	2 ms	644 KB	Output is correct
14	Correct	2 ms	644 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	484 KB	Output is correct
3	Correct	3 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	3 ms	644 KB	Output is correct
6	Correct	2 ms	644 KB	Output is correct
7	Correct	2 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	3 ms	644 KB	Output is correct
10	Correct	2 ms	644 KB	Output is correct
11	Correct	3 ms	644 KB	Output is correct
12	Correct	2 ms	644 KB	Output is correct
13	Correct	2 ms	644 KB	Output is correct
14	Correct	2 ms	644 KB	Output is correct
15	Correct	5 ms	644 KB	Output is correct
16	Correct	18 ms	2412 KB	Output is correct
17	Correct	25 ms	2416 KB	Output is correct
18	Correct	28 ms	2540 KB	Output is correct
19	Correct	33 ms	2540 KB	Output is correct
20	Correct	28 ms	2540 KB	Output is correct
21	Correct	30 ms	2540 KB	Output is correct
22	Correct	32 ms	2540 KB	Output is correct
23	Correct	33 ms	2540 KB	Output is correct
24	Correct	24 ms	2540 KB	Output is correct
25	Correct	27 ms	2540 KB	Output is correct
26	Correct	29 ms	2556 KB	Output is correct
27	Correct	34 ms	2556 KB	Output is correct
28	Correct	29 ms	2556 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	3 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	3 ms	644 KB	Output is correct
6	Correct	2 ms	644 KB	Output is correct
7	Correct	2 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	3 ms	644 KB	Output is correct
10	Correct	2 ms	644 KB	Output is correct
11	Correct	3 ms	644 KB	Output is correct
12	Correct	2 ms	644 KB	Output is correct
13	Correct	2 ms	644 KB	Output is correct
14	Correct	2 ms	644 KB	Output is correct
15	Correct	5 ms	644 KB	Output is correct
16	Correct	18 ms	2412 KB	Output is correct
17	Correct	25 ms	2416 KB	Output is correct
18	Correct	28 ms	2540 KB	Output is correct
19	Correct	33 ms	2540 KB	Output is correct
20	Correct	28 ms	2540 KB	Output is correct
21	Correct	30 ms	2540 KB	Output is correct
22	Correct	32 ms	2540 KB	Output is correct
23	Correct	33 ms	2540 KB	Output is correct
24	Correct	24 ms	2540 KB	Output is correct
25	Correct	27 ms	2540 KB	Output is correct
26	Correct	29 ms	2556 KB	Output is correct
27	Correct	34 ms	2556 KB	Output is correct
28	Correct	29 ms	2556 KB	Output is correct
29	Correct	2307 ms	56664 KB	Output is correct
30	Correct	2126 ms	56828 KB	Output is correct
31	Correct	2242 ms	58960 KB	Output is correct
32	Correct	2247 ms	59024 KB	Output is correct
33	Correct	2009 ms	59024 KB	Output is correct
34	Correct	2392 ms	59056 KB	Output is correct
35	Correct	2764 ms	59212 KB	Output is correct
36	Correct	2274 ms	59212 KB	Output is correct
37	Correct	2559 ms	59212 KB	Output is correct

답안 #61130

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