oj.uz

Submission #568629

# Submission time Handle Problem Language Result Execution time Memory
568629 2022-05-25T20:18:11 Z beaconmc Watching (JOI13_watching) C++14
100 / 100
 353 ms 31744 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 precomp[2003][2];

ll n,p,q;

vector<ll> places;


bool chk(ll a){
	FOR(i,0,2003) FOR(j,0,2) precomp[i][j] = 0;

	FOR(i,0,p+1) FOR(j,0,q+1) dp[i][j] = 0;

	FOR(i,0,n+1){
		ll sus = (upper_bound(places.begin(), places.end(), places[i] + a-1) - places.begin());
		ll sussy = (upper_bound(places.begin(), places.end(), places[i] + 2*a-1) - places.begin());

		precomp[i][0] = sus;
		precomp[i][1] = sussy;

	}



	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 = precomp[realsus][0];
			ll sussy = precomp[realsus][1];


			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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 340 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 596 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 217 ms 23980 KB Output is correct
4 Correct 34 ms 9668 KB Output is correct
5 Correct 22 ms 1620 KB Output is correct
6 Correct 353 ms 31744 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 16 ms 1636 KB Output is correct
9 Correct 19 ms 4156 KB Output is correct
10 Correct 33 ms 9300 KB Output is correct
11 Correct 21 ms 1728 KB Output is correct
12 Correct 126 ms 11844 KB Output is correct
13 Correct 7 ms 340 KB Output is correct
14 Correct 13 ms 448 KB Output is correct
15 Correct 7 ms 340 KB Output is correct