제출 #928526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928526		ByeWorld	구경하기 (JOI13_watching)	C++14	0 / 100	330 ms	31940 KiB

watching

#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 = 1e18+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;
		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';
		}
	}
	return (dp[n][q] <= 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
• Subtask 2: 0 / 50