oj.uz

답안 #85556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85556 2018-11-20T22:40:56 Z KCSC 구경하기 (JOI13_watching) C++14
100 / 100
 250 ms 14872 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 2005;

int pos[DIM], pos1[DIM], pos2[DIM], dp[DIM][DIM];

int main(void) {
#ifdef HOME
	freopen("watching.in", "r", stdin);
	freopen("watching.out", "w", stdout); 
#endif
	int n, p, q; cin >> n >> p >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> pos[i]; }
	sort(pos + 1, pos + n + 1);
	int le = 1, ri = 1000000000;
	while (le <= ri) {
		int md = (le + ri) / 2;
		for (int i = 1; i <= n; ++i) {
			pos1[i] = pos2[i] = 0;
			for (int j = 1; j < i; ++j) {
				if (pos[i] - md >= pos[j]) {
					pos1[i] = j; }
				if (pos[i] - md * 2 >= pos[j]) {
					pos2[i] = j; } }
			for (int j = 0; j <= i; ++j) {
				dp[i][j] = dp[pos2[i]][j] + 1;
				if (j > 0) {
					dp[i][j] = min(dp[i][j], dp[pos1[i]][j - 1]); } } } 	
		int ans = 1000000000;
		for (int i = 0; i <= min(p, n); ++i) {
			ans = min(ans, dp[n][i]); }
		if (ans <= q) {
			ri = md - 1; }
		else {
			le = md + 1; } }
	cout << le;
	return 0; }

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 840 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 908 KB Output is correct
7 Correct 3 ms 940 KB Output is correct
8 Correct 3 ms 1112 KB Output is correct
9 Correct 3 ms 1112 KB Output is correct
10 Correct 3 ms 1112 KB Output is correct
11 Correct 3 ms 1172 KB Output is correct
12 Correct 3 ms 1172 KB Output is correct
13 Correct 4 ms 1172 KB Output is correct
14 Correct 3 ms 1172 KB Output is correct
15 Correct 3 ms 1184 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 14520 KB Output is correct
2 Correct 2 ms 14520 KB Output is correct
3 Correct 199 ms 14544 KB Output is correct
4 Correct 200 ms 14544 KB Output is correct
5 Correct 202 ms 14584 KB Output is correct
6 Correct 190 ms 14584 KB Output is correct
7 Correct 232 ms 14728 KB Output is correct
8 Correct 210 ms 14728 KB Output is correct
9 Correct 250 ms 14768 KB Output is correct
10 Correct 202 ms 14788 KB Output is correct
11 Correct 203 ms 14788 KB Output is correct
12 Correct 213 ms 14828 KB Output is correct
13 Correct 212 ms 14828 KB Output is correct
14 Correct 214 ms 14872 KB Output is correct
15 Correct 223 ms 14872 KB Output is correct