답안 #399860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399860	2021-05-06T18:27:41 Z	nikatamliani	구경하기 (JOI13_watching)	C++14	100 / 100	245 ms	16068 KB

watching

#include <bits/stdc++.h>
using namespace std;
const int N = 2003;
int a[N], dp[N][N], n, q, p;
void mini(int &x, int y) {
	if(x > y) x = y;
}
bool check(int x) {
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			dp[i][j] = 1e9;
		}
		dp[0][i] = 0;
	}
	for(int i = 1; i <= n; ++i) {
		int id0 = i-1, id1 = i-1;
		while(id0 > 0 && a[i] - a[id0] + 1 <= x) --id0;
		while(id1 > 0 && a[i] - a[id1] + 1 <= 2*x) --id1;
		for(int j = 0; j <= p; ++j) {
			dp[i][j] = dp[id1][j]+1;
			if(j > 0) {
				mini(dp[i][j], dp[id0][j-1]);
			}
		}
	}
	return dp[n][p] <= q;
}
int main() {
	cin >> n >> p >> q;
	if(p + q >= n) {
		cout << 1 << '\n';
		return 0;
	}
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	sort(a+1, a+n+1);
	int l = 1, r = 1e9, ans = -1;
	while(r >= l) {
		int m = l + r >> 1;
		if(check(m)) {
			ans = m;
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	cout << ans << endl;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int m = l + r >> 1;
      |           ~~^~~

Subtask #1

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	90 ms	15948 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	90 ms	15992 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	90 ms	15984 KB	Output is correct
8	Correct	86 ms	15948 KB	Output is correct
9	Correct	87 ms	16068 KB	Output is correct
10	Correct	94 ms	15984 KB	Output is correct
11	Correct	88 ms	15920 KB	Output is correct
12	Correct	88 ms	15948 KB	Output is correct
13	Correct	89 ms	15948 KB	Output is correct
14	Correct	87 ms	15992 KB	Output is correct
15	Correct	88 ms	16068 KB	Output is correct

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	159 ms	16000 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	115 ms	15948 KB	Output is correct
8	Correct	119 ms	15908 KB	Output is correct
9	Correct	161 ms	15948 KB	Output is correct
10	Correct	245 ms	16000 KB	Output is correct
11	Correct	105 ms	15948 KB	Output is correct
12	Correct	186 ms	15948 KB	Output is correct
13	Correct	120 ms	15948 KB	Output is correct
14	Correct	112 ms	16004 KB	Output is correct
15	Correct	109 ms	15948 KB	Output is correct