Submission #958617

#	Time	Username	Problem	Language	Result	Execution time	Memory
958617		pcc	Watching (JOI13_watching)	C++17	100 / 100	169 ms	16472 KiB

watching

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2020;
int dp[mxn][mxn];
int N;
int arr[mxn];
int pt1,pt2;
int P,Q;

bool check(int len){
	pt1 = 0,pt2 = 0;
	for(int i = 1;i<=N;i++){
		while(arr[i]-arr[pt1]>=len)pt1++;
		while(arr[i]-arr[pt2]>=len*2)pt2++;
		for(int j = 0;j<=N;j++){
			dp[i][j] = 1e9;
			if(j)dp[i][j] = min(dp[i][j],dp[pt2-1][j-1]);
			dp[i][j] = min(dp[i][j],dp[pt1-1][j]+1);
		}
	}
	return dp[N][Q]<=P;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>P>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	if(P+Q>=N){
		cout<<1;
		return 0;
	}
	arr[0] = -1e9-10;
	sort(arr+1,arr+N+1);
	int l = 0,r = 1e9;
	while(l != r){
		int mid = (l+r)>>1;
		if(check(mid))r = mid;
		else l = mid+1;
	}
	cout<<l<<'\n';
	return 0;
}

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