oj.uz

답안 #77018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77018 2018-09-20T04:39:55 Z shoemakerjo 구경하기 (JOI13_watching) C++14
100 / 100
 138 ms 16744 KB 
#include <bits/stdc++.h>

using namespace std;

#define maxn 2002

const int inf = 1000000000;

int N, P, Q;
vector<int> nums;
int dp[maxn][maxn];

bool go(int mid) {
	//option is to end at me with a small or end at me with a large
	//we will just consider ending exactly at some guy (e.g. the last guy)
	dp[0][0] = 0;
	int pbef = 0;
	int qbef = 0;

	for (int i = 1 ; i <= N; i++) {
		while (pbef != i && nums[i] - nums[pbef+1] >= mid) {
			pbef++;
		}
		while (qbef != i && nums[i] - nums[qbef+1] >= 2*mid) {
			qbef++;
		}
		for (int j = 0; j <= i && j <= P;  j++) {
			dp[i][j] = inf;
			if (j > 0) dp[i][j] = min(dp[i][j], dp[pbef][j-1]);
			dp[i][j] = min(dp[i][j], dp[qbef][j]+1);
		}
	}
	for (int i = 0; i <= P; i++) {
		if (dp[N][i] <= Q) return true;
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	for (int i = 0; i < maxn; i++) {
		for (int j = 0; j < maxn; j++) dp[i][j] = inf;
	}
	cin >> N >> P >> Q;
	if (P + Q >= N) {
		cout << 1 << endl;
		return 0;
	}
	int cur;
	for (int i = 0; i < N; i++) {
		cin >> cur;
		nums.push_back(cur);
	}
	nums.push_back(-1);
	sort(nums.begin(), nums.end());
	int lo = 1, hi = inf;
	while (lo < hi) {
		int mid = (lo+hi)/2;
		if (go(mid)) {
			hi = mid;
		}
		else lo = mid+1;
	}
	cout << lo << endl;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 15992 KB Output is correct
2 Correct 15 ms 16116 KB Output is correct
3 Correct 16 ms 16200 KB Output is correct
4 Correct 15 ms 16296 KB Output is correct
5 Correct 15 ms 16296 KB Output is correct
6 Correct 15 ms 16296 KB Output is correct
7 Correct 15 ms 16324 KB Output is correct
8 Correct 15 ms 16372 KB Output is correct
9 Correct 15 ms 16372 KB Output is correct
10 Correct 15 ms 16372 KB Output is correct
11 Correct 15 ms 16372 KB Output is correct
12 Correct 15 ms 16372 KB Output is correct
13 Correct 15 ms 16372 KB Output is correct
14 Correct 15 ms 16392 KB Output is correct
15 Correct 15 ms 16392 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 16392 KB Output is correct
2 Correct 14 ms 16392 KB Output is correct
3 Correct 15 ms 16404 KB Output is correct
4 Correct 14 ms 16420 KB Output is correct
5 Correct 15 ms 16452 KB Output is correct
6 Correct 20 ms 16484 KB Output is correct
7 Correct 18 ms 16516 KB Output is correct
8 Correct 31 ms 16664 KB Output is correct
9 Correct 90 ms 16664 KB Output is correct
10 Correct 138 ms 16664 KB Output is correct
11 Correct 31 ms 16664 KB Output is correct
12 Correct 102 ms 16744 KB Output is correct
13 Correct 18 ms 16744 KB Output is correct
14 Correct 22 ms 16744 KB Output is correct
15 Correct 19 ms 16744 KB Output is correct