oj.uz

Submission #568625

# Submission time Handle Problem Language Result Execution time Memory
568625 2022-05-25T20:14:02 Z beaconmc Watching (JOI13_watching) C++14
50 / 100
 1000 ms 31700 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());
	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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 31676 KB Output is correct
2 Correct 129 ms 31672 KB Output is correct
3 Correct 130 ms 31668 KB Output is correct
4 Correct 131 ms 31676 KB Output is correct
5 Correct 131 ms 31572 KB Output is correct
6 Correct 130 ms 31680 KB Output is correct
7 Correct 128 ms 31700 KB Output is correct
8 Correct 128 ms 31668 KB Output is correct
9 Correct 129 ms 31676 KB Output is correct
10 Correct 140 ms 31680 KB Output is correct
11 Correct 131 ms 31700 KB Output is correct
12 Correct 132 ms 31688 KB Output is correct
13 Correct 125 ms 31680 KB Output is correct
14 Correct 128 ms 31676 KB Output is correct
15 Correct 127 ms 31680 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 31700 KB Output is correct
2 Correct 131 ms 31672 KB Output is correct
3 Execution timed out 1092 ms 31700 KB Time limit exceeded
4 Halted 0 ms 0 KB -