Submission #568629

#	Time	Username	Problem	Language	Result	Execution time	Memory
568629		beaconmc	Watching (JOI13_watching)	C++14	100 / 100	353 ms	31744 KiB

watching

#include <bits/stdc++.h>

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)

using namespace std;

ll dp[2003][2003];
ll precomp[2003][2];

ll n,p,q;

vector<ll> places;


bool chk(ll a){
	FOR(i,0,2003) FOR(j,0,2) precomp[i][j] = 0;

	FOR(i,0,p+1) FOR(j,0,q+1) dp[i][j] = 0;

	FOR(i,0,n+1){
		ll sus = (upper_bound(places.begin(), places.end(), places[i] + a-1) - places.begin());
		ll sussy = (upper_bound(places.begin(), places.end(), places[i] + 2*a-1) - places.begin());

		precomp[i][0] = sus;
		precomp[i][1] = sussy;

	}



	FOR(i,0,n+1){
		if (i>p) break;
		FOR(j,0,n+1){
			if (j>q) break;
			ll realsus = dp[i][j];
			if (realsus==n) break;

			ll sus = precomp[realsus][0];
			ll sussy = precomp[realsus][1];


			dp[i][j+1] = max(dp[i][j+1] , sussy);
			dp[i+1][j] = max(dp[i+1][j], sus);
		}
	}



	FOR(i,0,p+1){
		FOR(j,0,q+1){
			if (dp[i][j] == n) return 1;
		}
	}



	return 0;

}

int main(){
	cin >>n>>p>>q;
	FOR(i,0,n){ 
		ll temp;
		cin >> temp;
		places.push_back(temp);
	}
	sort(places.begin(), places.end());
	p = min(p,n);
	q = min(q,n);


	ll lo = 0, hi = 10000000000;
	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (chk(mid)){
			hi = mid;
		}
		else lo = mid + 1;
	}
	cout << lo;

}

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