oj.uz

Submission #568617

# Submission time Handle Problem Language Result Execution time Memory
568617 2022-05-25T20:04:59 Z beaconmc Watching (JOI13_watching) C++14
0 / 100
 146 ms 31720 KB 
#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];

			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+1) return 1;
		}
	}



	return 0;

}

int main(){
	cin >>n>>p>>q;
	places.push_back(0);
	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.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 31692 KB Output is correct
2 Correct 138 ms 31676 KB Output is correct
3 Incorrect 128 ms 31680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 31720 KB Output is correct
2 Incorrect 146 ms 31572 KB Output isn't correct
3 Halted 0 ms 0 KB -