제출 #161133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
161133		Knps4422	구경하기 (JOI13_watching)	C++14	100 / 100	356 ms	16248 KiB

watching

#include <bits/stdc++.h>
#define in cin
using namespace std;
int n ,p ,q;
vector<int> a;
int nx[2005],nxd[2005];
int dp[2005][2005]; // nr minim de tip 2 pentru maxim i de tip 1
int check(int w){
    //cout << "START OF TEST :" << w << '\n';
	for(int i = 1; i <= n; i++){
		nx[i] = upper_bound(a.begin(),a.end(),a[i]+w-1)-a.begin();
	}
	for(int i = 1; i <= n; i++){
		nxd[i] = upper_bound(a.begin(),a.end(),a[i]+2*w-1)-a.begin();
        //cout << a[i]+2*w << ' ' << nxd[i];
        //cout<< '\n';
	}
	//cout << "END OF TEST\n";
	//
	for(int i = n ; i > 0 ;i--)
		for(int k = 0 ; k <= p ; k++)
			dp[i][k] = 0;
	//
	for(int i = n ; i > 0 ;i--){
		for(int k = 0 ; k <= p ; k++){
			dp[i][k] = dp[nxd[i]][k] + 1;
			if(k > 0)
			dp[i][k] = min(dp[nx[i]][k-1],dp[i][k]);
		}
	}
	//
	if(dp[1][p] <= q)return 1;
	else return 0;
}
ifstream fin("in1.i");
int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    in >> n >> p >> q;
    int nt;
    a.push_back(0);
    for(int i = 1; i <= n; i++){
    	in >> nt;
    	a.push_back(nt);
    }
    if(p + q >= n){
    	cout << 1;
    	return 0;
    }
    sort(a.begin(),a.end());
    int l = 1 , r = 1e9;
    while(l < r){
    	int mid = (l+r)/2;
    	if(check(mid)){
    		r = mid;
    	}else{
    		l = mid+1;
    	}
    }
    cout << l;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50