Submission #77018

#	Time	Username	Problem	Language	Result	Execution time	Memory
77018		shoemakerjo	Watching (JOI13_watching)	C++14	100 / 100	138 ms	16744 KiB

watching

#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 / 50
• Subtask 2: 50 / 50