oj.uz

답안 #26824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26824 2017-07-06T07:42:40 Z szawinis 구경하기 (JOI13_watching) C++14
100 / 100
 276 ms 17828 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX = (2e3)+1, INF = 1e8;

int n, p, q, a[MAX], dp[MAX][MAX];
bool check(int len) {
	for(int i = 1, x = 1, y = 1; i <= n; i++) {
		while(a[i] - a[x] + 1 > len) x++;
		while(a[i] - a[y] + 1 > 2*len) y++;
		for(int j = 0; j <= min(p, n); j++) dp[i][j] = dp[y-1][j] + 1;
		for(int j = 1; j <= min(p, n); j++) dp[i][j] = min(dp[x-1][j-1], dp[i][j]);
	}
	bool ret = false;
	for(int j = 0; j <= min(p, n); j++) ret |= dp[n][j] <= q;
	return ret;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> p >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1, a+n+1);
	int l = 1, r = 1e9;
	while(l < r) {
		int mid = l+r >> 1;
		if(check(mid)) r = mid;
		else l = mid+1;
	}
	cout << l;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:25:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
              ^

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 17828 KB Output is correct
2 Correct 0 ms 17828 KB Output is correct
3 Correct 199 ms 17828 KB Output is correct
4 Correct 263 ms 17828 KB Output is correct
5 Correct 13 ms 17828 KB Output is correct
6 Correct 276 ms 17828 KB Output is correct
7 Correct 6 ms 17828 KB Output is correct
8 Correct 16 ms 17828 KB Output is correct
9 Correct 96 ms 17828 KB Output is correct
10 Correct 246 ms 17828 KB Output is correct
11 Correct 16 ms 17828 KB Output is correct
12 Correct 123 ms 17828 KB Output is correct
13 Correct 0 ms 17828 KB Output is correct
14 Correct 3 ms 17828 KB Output is correct
15 Correct 6 ms 17828 KB Output is correct