Submission #573502

#	Time	Username	Problem	Language	Result	Execution time	Memory
573502		dsyz	Watching (JOI13_watching)	C++17	100 / 100	294 ms	31656 KiB

watching

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (2005)
ll N,P,Q;
ll arr[MAXN];
bool bs(ll w){
	ll dp[N][P + 1]; //number of events covered, number of small cameras, value: number of big cameras needed
	memset(dp,0,sizeof(dp));
	for(ll i = N - 1;i >= 0;i--){
		ll y = lower_bound(arr,arr + N,arr[i] + 2 * w) - arr;
		ll x = lower_bound(arr,arr + N,arr[i] + w) - arr;
		if (y == N) dp[i][0] = 1;
		else dp[i][0] = dp[y][0] + 1;
		for(ll j = 1;j <= P;j++) {
			if (y == N) dp[i][j] = 1;
			else dp[i][j] = dp[y][j] + 1;
			if (x == N) dp[i][j] = 0;
			else dp[i][j] = min(dp[i][j], dp[x][j - 1]);
		}
	}
	return dp[0][P] <= Q;
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>P>>Q;
	P = min(P,N);
	Q = min(Q,N);
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	sort(arr,arr + N);
	ll low = 0;
	ll high = 1000000000;
	while(high - low > 1){
		ll mid = (high + low) / 2;
		if(bs(mid)){
			high = mid;
		}else{
			low = mid;
		}
	}
	cout<<high<<'\n';
}

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