oj.uz

Submission #77017

# Submission time Handle Problem Language Result Execution time Memory
77017 2018-09-20T04:38:21 Z shoemakerjo Watching (JOI13_watching) C++14
0 / 100
 16 ms 16152 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) return 1;
	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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15992 KB Output is correct
2 Runtime error 14 ms 15992 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16024 KB Output is correct
2 Runtime error 14 ms 16152 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -