Submission #77018

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
77018	2018-09-20T04:39:55 Z	shoemakerjo	Watching (JOI13_watching)	C++14	100 / 100	138 ms	16744 KB

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.0 / 50.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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