Submission #51435

#	Time	Username	Problem	Language	Result	Execution time	Memory
51435		DrumpfTheGodEmperor	Watching (JOI13_watching)	C++14	100 / 100	154 ms	16380 KiB

watching

#include <bits/stdc++.h>
#define INF 1000000007
#define pb push_back
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
using namespace std;
int n,p,q,a[2001],poss[2001],posl[2001],dp[2001][2001];
bool check(int w) {
	fw (i,0,n) {
		poss[i]=upper_bound(a,a+n,a[i]+w-1)-a;
		posl[i]=upper_bound(a,a+n,a[i]+2*w-1)-a;
	}
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0; //DP[i][j] stores not the maximal place you can reach, but minimal you can't reach
	fw (i,0,p+1) fw (j,0,q+1) if (dp[i][j]!=-1) {
		if (dp[i][j]==n) return true;
		dp[i+1][j]=max(dp[i+1][j],poss[dp[i][j]]);
		dp[i][j+1]=max(dp[i][j+1],posl[dp[i][j]]);
	}
	return false;
}
int ans(int l,int r) {
	int mid=(l+r)/2;
	if (l==r) return l;
	bool temp=check(mid);
	if (temp) return ans(l,mid);
	else return ans(mid+1,r);
}
signed main() {
	//freopen("aome.inp","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>p>>q;
	fw (i,0,n) cin>>a[i]; 
	if (p+q>=n) {cout<<"1"; return 0;}
	sort(a,a+n);
	/*
	DP[i][j]: Furthest position you can reach with i small cameras and j big ones.
	Binary search for the answer, then create a board for the furthest position of each one.
	Total complexity: O(PQ * log2(1e9))
	*/
	cout<<ans(1,1000000000);
	return 0;
}

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