Submission #51476

#	Time	Username	Problem	Language	Result	Execution time	Memory
51476		futanaristic	Watching (JOI13_watching)	C++14	100 / 100	309 ms	32124 KiB

watching

#include <bits/stdc++.h>
#define INF 1000000007
#define pb push_back
#define int long long
#define ub upper_bound
using namespace std;
int n,p,q,a[2001],S[2001],B[2001],dp[2001][2001];
bool legit(int W) {
	for (int i = 0 ; i < n ; i ++) {
		S[i]=ub(a,a+n,a[i]+W-1)-a;
		B[i]=ub(a,a+n,a[i]+2*W-1)-a;
	}
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0;  
	for (int i = 0 ; i <= p ; i ++)
	for (int j = 0 ; j <= q ; j ++) 
	if (dp[i][j]!=-1) {
		if (dp[i][j]==n) return true;
		dp[i+1][j]=max(dp[i+1][j],S[dp[i][j]]);
		dp[i][j+1]=max(dp[i][j+1],B[dp[i][j]]);
	}
	return false;
}

signed main() {
	
	cin >> n>>p>>q;
	for (int i = 0 ; i < n ; i ++) cin>>a[i]; 
	if (p+q>=n) {cout<<"1"; return 0;}
	sort(a,a+n);
	int L = 1 ,R = 1000000000;
	while(L <= R){
		if (L == R)break;
		int M = L + (R-L)/2;
		if(legit(M)) R = M;
		else L = M + 1;
	} 
	cout << L;
	return 0;
}

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