oj.uz

Submission #93550

# Submission time Handle Problem Language Result Execution time Memory
93550 2019-01-09T14:16:06 Z Dat160601 Watching (JOI13_watching) C++14
100 / 100
 375 ms 16156 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, p, q, x, dp[2007][2007], jump[2][2007];
vector <int> val;

bool check(int x){
	for(int i = 0; i <= n + 1; i++){
		for(int j = 0; j <= p; j++){
			dp[i][j] = -1e9;
		}
	}
	dp[1][0] = q;
	for(int i = 1; i <= n; i++){
		int pos = upper_bound(val.begin(), val.end(), val[i - 1] + x - 1) - val.begin();
		jump[0][i] = pos - (i - 1);
		pos = upper_bound(val.begin(), val.end(), min((long long)2e9, val[i - 1] + 2LL * x - 1)) - val.begin();
		jump[1][i] = pos - (i - 1);
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= p; j++){
			dp[i + jump[1][i]][j] = max(dp[i + jump[1][i]][j], dp[i][j] - 1);
			if(j < p){
				dp[i + jump[0][i]][j + 1] = max(dp[i + jump[0][i]][j + 1], dp[i][j]);
			}
		}
	}
	int ans = -1e9;
	for(int i = 0; i <= p; i++) ans = max(ans, dp[n + 1][i]);
	return (ans >= 0);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> p >> q;
	for(int i = 1; i <= n; i++){
		cin >> x;
		val.pb(x);
	}
	sort(val.begin(), val.end());
	if(p + q >= n) return cout << 1, 0;
	int l = 1, r = 1e9, mid = (l + r) >> 1;
	while(l < r){
		if(check(mid)) r = mid;
		else l = mid + 1;
		mid = (l + r) >> 1;
	}
	cout << l;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 764 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 348 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 2 ms 732 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 728 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 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 11 ms 8412 KB Output is correct
2 Correct 2 ms 376 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 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 15 ms 8568 KB Output is correct
8 Correct 40 ms 9336 KB Output is correct
9 Correct 152 ms 14388 KB Output is correct
10 Correct 375 ms 16156 KB Output is correct
11 Correct 31 ms 9080 KB Output is correct
12 Correct 192 ms 16132 KB Output is correct
13 Correct 16 ms 8440 KB Output is correct
14 Correct 17 ms 8568 KB Output is correct
15 Correct 17 ms 8568 KB Output is correct