Submission #93550

#	Time	Username	Problem	Language	Result	Execution time	Memory
93550		Dat160601	Watching (JOI13_watching)	C++14	100 / 100	375 ms	16156 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, p, q, x, dp[2007][2007], jump[2][2007];
vector <int> val;

bool check(int x){
	for(int i = 0; i <= n + 1; i++){
		for(int j = 0; j <= p; j++){
			dp[i][j] = -1e9;
		}
	}
	dp[1][0] = q;
	for(int i = 1; i <= n; i++){
		int pos = upper_bound(val.begin(), val.end(), val[i - 1] + x - 1) - val.begin();
		jump[0][i] = pos - (i - 1);
		pos = upper_bound(val.begin(), val.end(), min((long long)2e9, val[i - 1] + 2LL * x - 1)) - val.begin();
		jump[1][i] = pos - (i - 1);
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= p; j++){
			dp[i + jump[1][i]][j] = max(dp[i + jump[1][i]][j], dp[i][j] - 1);
			if(j < p){
				dp[i + jump[0][i]][j + 1] = max(dp[i + jump[0][i]][j + 1], dp[i][j]);
			}
		}
	}
	int ans = -1e9;
	for(int i = 0; i <= p; i++) ans = max(ans, dp[n + 1][i]);
	return (ans >= 0);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> p >> q;
	for(int i = 1; i <= n; i++){
		cin >> x;
		val.pb(x);
	}
	sort(val.begin(), val.end());
	if(p + q >= n) return cout << 1, 0;
	int l = 1, r = 1e9, mid = (l + r) >> 1;
	while(l < r){
		if(check(mid)) r = mid;
		else l = mid + 1;
		mid = (l + r) >> 1;
	}
	cout << l;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50