oj.uz

Submission #568624

# Submission time Handle Problem Language Result Execution time Memory
568624 2022-05-25T20:13:12 Z beaconmc Watching (JOI13_watching) C++14
0 / 100
 1000 ms 64064 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];
			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.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 31572 KB Output is correct
2 Correct 145 ms 31672 KB Output is correct
3 Correct 142 ms 31672 KB Output is correct
4 Runtime error 157 ms 64064 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 31700 KB Output is correct
2 Correct 130 ms 31668 KB Output is correct
3 Execution timed out 1080 ms 31700 KB Time limit exceeded
4 Halted 0 ms 0 KB -