oj.uz

Submission #928527

# Submission time Handle Problem Language Result Execution time Memory
928527 2024-02-16T14:57:50 Z ByeWorld Watching (JOI13_watching) C++14
100 / 100
 126 ms 16428 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
//#define int long long
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int INF = 1e9+10;
const int MAXN = 2e3+10;

int n, p, q;
vector <int> a;
int dp[MAXN][MAXN];

bool cek(int x){ // lengthnya x
	for(int j=0; j<=n; j++) dp[0][j] = 0; 
	for(int i=1; i<=n; i++){
		for(int j=0; j<=n; j++) dp[i][j] = INF;
	}

	for(int i=1; i<=n; i++){ // mau kenain a[i]
		// a[i]-x+1 -- a[i]
		auto it1 = lower_bound(a.begin(), a.end(), a[i]-x+1); // small
		int idx = -1;
		if(it1 == a.begin()) idx = 0; // bisa karena negatif
		else {
			it1--; // ambil belakangnya
			idx = (it1-a.begin());
		}
		//cout << i << ' ' <<a[i]<< ' ' << idx << " p\n";
		auto it2 = lower_bound(a.begin(), a.end(), a[i]-2*x+1); // big
		int idx2 = -1;
		if(it2 == a.begin()) idx2 = 0;
		else {
			it2--; // ambil belakangnya
			idx2 = (it2-a.begin());
		} 
		//cout << i << ' ' <<a[i]<< ' ' << idx2 << " p\n";

		for(int j=0; j<=min(i, q); j++){  // num big camera
			dp[i][j] = min(dp[i][j], dp[idx][j]+1);	//small
			if(j!=0)
				dp[i][j] = min(dp[i][j], dp[idx2][j-1]); //big
			//cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
		}
	}
	int mn = INF;
	for(int i=0; i<=q; i++) mn = min(mn, dp[n][i]);
	return (mn <= p); // pake q big, harus <= small
} 
void bin(){
	int l=1, r=INF, mid=0, cnt=-1;
	while(l<=r){
		mid = md;
		if(cek(md)){
			r = mid-1; cnt = mid;
		} else l = mid+1;
	}
	cout << cnt << '\n';
}
signed main(){
	cin >> n >> p >> q; // small - big
	q = min(q, n);
	a.pb(0);
	for(int i=1; i<=n; i++){
		int x; cin >> x;
		a.pb(x);
	}
	sort(a.begin(), a.end());
	bin();
	//cout << cek(1) << " p\n";
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2548 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 16428 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 126 ms 15964 KB Output is correct
4 Correct 55 ms 15964 KB Output is correct
5 Correct 115 ms 15960 KB Output is correct
6 Correct 119 ms 15964 KB Output is correct
7 Correct 47 ms 15964 KB Output is correct
8 Correct 93 ms 15964 KB Output is correct
9 Correct 57 ms 15964 KB Output is correct
10 Correct 55 ms 15964 KB Output is correct
11 Correct 120 ms 16192 KB Output is correct
12 Correct 102 ms 16204 KB Output is correct
13 Correct 50 ms 16216 KB Output is correct
14 Correct 48 ms 16196 KB Output is correct
15 Correct 50 ms 16220 KB Output is correct