Submission #170344

#	Time	Username	Problem	Language	Result	Execution time	Memory
170344		ngmh	Watching (JOI13_watching)	C++11	50 / 100	1068 ms	31996 KiB

watching

#include <bits/stdc++.h>
using namespace std;

long long n, p, q, a[2005], mini, medi, maxi, far, dp[2005][2005];

long long need(long long idx, long long big, long long w){
	if(idx < 0) return 0;
	if(dp[idx][big] != -1) return dp[idx][big];
	dp[idx][big] = INT_MAX;
	if(big > 0){
		far = upper_bound(a, a+n, a[idx]-w-w)-a;
		far--;
		dp[idx][big] = min(dp[idx][big], need(far, big-1, w));
	}
	far = upper_bound(a, a+n, a[idx]-w)-a;
	far--;
	dp[idx][big] = min(dp[idx][big], (long long) (need(far, big, w)+1));
	return dp[idx][big];
}

int main(){
	cin >> n >> p >> q;
	if(p+q >= n){
		cout << 1;
		return 0;
	}
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a+n);
	mini = 0; maxi = a[n-1]+1;
	while(mini < maxi){
		medi = mini+(maxi-mini)/2;
		memset(dp, -1, sizeof(dp));
		if(need(n-1, q, medi) <= p) maxi = medi;
		else mini = medi+1;
	}
	cout << mini;
}

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