제출 #568624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568624		beaconmc	구경하기 (JOI13_watching)	C++14	0 / 100	1080 ms	64064 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 n,p,q;

vector<ll> places;


bool chk(ll a){

	FOR(i,0,2002) FOR(j,0,2002) dp[i][j] = 0;




	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 = (upper_bound(places.begin(), places.end(), places[realsus] + a-1) - places.begin());
			ll sussy = (upper_bound(places.begin(), places.end(), places[realsus] + 2*a-1) - places.begin());




			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());


	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: 0 / 50
• Subtask 2: 0 / 50