oj.uz

Submission #928529

# Submission time Handle Problem Language Result Execution time Memory
928529 2024-02-16T14:58:11 Z ByeWorld Watching (JOI13_watching) C++14
0 / 100
 131 ms 16180 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 = dp[n][q];
	//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
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 1 ms 348 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 16172 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 131 ms 16180 KB Output isn't correct
4 Halted 0 ms 0 KB -