oj.uz

Submission #568634

# Submission time Handle Problem Language Result Execution time Memory
568634 2022-05-25T21:01:09 Z beaconmc Watching (JOI13_watching) C++14
50 / 100
 1000 ms 23852 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,p+1) FOR(j,0,q+1) 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 1084 ms 23852 KB Time limit exceeded
4 Halted 0 ms 0 KB -