답안 #51555 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51555	2018-06-18T14:29:33 Z	Vinhspm	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3497 ms	136496 KB

joioi

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
const int N = 2009;
const int oo = 1e9 + 10;
const int mod = 1e9 + 7;
int n, m, ans = oo, imin = oo;
int a[N][N], tmp[N][N], Rmin[N][N], Rmax[N][N], pos[N];
void _rorate()	{
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)
		tmp[j][n - i + 1] = a[i][j];
	swap(n, m);
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)
		a[i][j] = tmp[i][j];
}
bool check(int val)	{ 
	// we save 
	for(int i = 1; i <= n; ++i)	{
		pos[i] = m + 1;
		for(int j = 1; j <= m; ++j) if(a[i][j] - imin > val) {
			pos[i] = j; break;
		}
	}
	for (int i = 1; i <= n; ++i)	{
		Rmin[i][m + 1] = oo, Rmax[i][m + 1] = 0;
		for (int j = m; j >= 1; --j) {
			Rmin[i][j] = min(Rmin[i][j + 1], a[i][j]);
			Rmax[i][j] = max(Rmax[i][j + 1], a[i][j]);
		}
	}
	int cur = oo, curmin = oo, curmax = 0;
	for(int i = 1; i <= n; ++i) 	{
		cur = min(cur, pos[i] - 1);
		curmin = min(curmin, Rmin[i][cur + 1]);
		curmax = max(curmax, Rmax[i][cur + 1]);
	}
	return ( curmax - curmin <= val );
}
void solve()	{
	int l = 0, r = oo;
	while(r > l) 	{
		int mid = (l + r) /2;
		if(check(mid) == true) r = mid;
		else l = mid + 1;
	}
	if(check(l)) ans = min(ans, l);
}
signed main()
{
	//freopen("test.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j], imin = min(imin, a[i][j]); 
	solve(); 
	_rorate(); solve();
	_rorate(); solve();
	_rorate(); solve();
	cout << ans;
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	0 ms	544 KB	Output is correct
4	Correct	3 ms	716 KB	Output is correct
5	Correct	3 ms	716 KB	Output is correct
6	Correct	3 ms	716 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	3 ms	824 KB	Output is correct
9	Correct	3 ms	824 KB	Output is correct
10	Correct	3 ms	824 KB	Output is correct
11	Correct	3 ms	824 KB	Output is correct
12	Correct	4 ms	824 KB	Output is correct
13	Correct	3 ms	824 KB	Output is correct
14	Correct	4 ms	824 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	0 ms	544 KB	Output is correct
4	Correct	3 ms	716 KB	Output is correct
5	Correct	3 ms	716 KB	Output is correct
6	Correct	3 ms	716 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	3 ms	824 KB	Output is correct
9	Correct	3 ms	824 KB	Output is correct
10	Correct	3 ms	824 KB	Output is correct
11	Correct	3 ms	824 KB	Output is correct
12	Correct	4 ms	824 KB	Output is correct
13	Correct	3 ms	824 KB	Output is correct
14	Correct	4 ms	824 KB	Output is correct
15	Correct	8 ms	4024 KB	Output is correct
16	Correct	41 ms	4628 KB	Output is correct
17	Correct	40 ms	4748 KB	Output is correct
18	Correct	40 ms	4748 KB	Output is correct
19	Correct	37 ms	4748 KB	Output is correct
20	Correct	34 ms	4748 KB	Output is correct
21	Correct	42 ms	4748 KB	Output is correct
22	Correct	37 ms	4808 KB	Output is correct
23	Correct	36 ms	4808 KB	Output is correct
24	Correct	35 ms	4808 KB	Output is correct
25	Correct	44 ms	4808 KB	Output is correct
26	Correct	41 ms	4808 KB	Output is correct
27	Correct	39 ms	4820 KB	Output is correct
28	Correct	38 ms	4820 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	0 ms	544 KB	Output is correct
4	Correct	3 ms	716 KB	Output is correct
5	Correct	3 ms	716 KB	Output is correct
6	Correct	3 ms	716 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	3 ms	824 KB	Output is correct
9	Correct	3 ms	824 KB	Output is correct
10	Correct	3 ms	824 KB	Output is correct
11	Correct	3 ms	824 KB	Output is correct
12	Correct	4 ms	824 KB	Output is correct
13	Correct	3 ms	824 KB	Output is correct
14	Correct	4 ms	824 KB	Output is correct
15	Correct	8 ms	4024 KB	Output is correct
16	Correct	41 ms	4628 KB	Output is correct
17	Correct	40 ms	4748 KB	Output is correct
18	Correct	40 ms	4748 KB	Output is correct
19	Correct	37 ms	4748 KB	Output is correct
20	Correct	34 ms	4748 KB	Output is correct
21	Correct	42 ms	4748 KB	Output is correct
22	Correct	37 ms	4808 KB	Output is correct
23	Correct	36 ms	4808 KB	Output is correct
24	Correct	35 ms	4808 KB	Output is correct
25	Correct	44 ms	4808 KB	Output is correct
26	Correct	41 ms	4808 KB	Output is correct
27	Correct	39 ms	4820 KB	Output is correct
28	Correct	38 ms	4820 KB	Output is correct
29	Correct	3073 ms	64060 KB	Output is correct
30	Correct	3010 ms	64060 KB	Output is correct
31	Correct	3391 ms	64060 KB	Output is correct
32	Correct	3239 ms	64060 KB	Output is correct
33	Correct	2863 ms	64060 KB	Output is correct
34	Correct	3208 ms	64060 KB	Output is correct
35	Correct	3455 ms	64060 KB	Output is correct
36	Correct	3144 ms	97348 KB	Output is correct
37	Correct	3497 ms	136496 KB	Output is correct

답안 #51555

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