oj.uz

Submission #161133

# Submission time Handle Problem Language Result Execution time Memory
161133 2019-10-31T16:14:19 Z Knps4422 Watching (JOI13_watching) C++14
100 / 100
 356 ms 16248 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 3 ms 764 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 3 ms 760 KB Output is correct
14 Correct 3 ms 760 KB Output is correct
15 Correct 2 ms 760 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8440 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 416 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 17 ms 8568 KB Output is correct
8 Correct 38 ms 9464 KB Output is correct
9 Correct 150 ms 14348 KB Output is correct
10 Correct 356 ms 16192 KB Output is correct
11 Correct 33 ms 9084 KB Output is correct
12 Correct 192 ms 16248 KB Output is correct
13 Correct 18 ms 8568 KB Output is correct
14 Correct 21 ms 8568 KB Output is correct
15 Correct 19 ms 8568 KB Output is correct