Submission #379552

#	Time	Username	Problem	Language	Result	Execution time	Memory
379552		penguin133	Watching (JOI13_watching)	C++14	100 / 100	250 ms	16236 KiB

watching

#include <bits/stdc++.h>
using namespace std;
int n,p,q,s = 1, e= 1e9 + 5, ans = 1e9 + 5;
int dp[2005][2005], A[2005];
bool c(int x){
	for(int i=1;i<=n;i++){
		int l = 1, r = 1;
		while(A[i] - A[l] >= x)l++;
		while(A[i] - A[r] >= 2*x)r++;
		for(int j=0;j<=p;j++){
			if(j == 0)dp[i][j] = dp[r-1][j] + 1;
			else dp[i][j] = min(dp[l-1][j-1], dp[r-1][j] + 1);
		}
	}
	return dp[n][p] <= q;
}
int main(){
	cin >> n >> p >> q;
	for(int i=1;i<=n;i++)cin >> A[i];
	if(p + q >= n){
		cout << 1;
		exit(0);
	}
	sort(A+1, A+n+1);
	while(s <= e){
		int m = (s + e)/2;
		memset(dp, 0, sizeof(dp));
		if(c(m)){
			ans = m;
			e = m - 1;
		}
		else s = m + 1;
	}
	cout << ans;
}

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