oj.uz

Submission #197774

# Submission time Handle Problem Language Result Execution time Memory
197774 2020-01-22T22:59:26 Z Malomalomalomalo Watching (JOI13_watching) C++14
100 / 100
 348 ms 16248 KB 
#include <bits/stdc++.h>
#define gmin(x,y) x=min(x,y)
#define all(c) c.begin(), c.end()
using namespace std;

const int N = 2e3 + 5;

int dp[N][N];
const int inf = 1e9;

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n,p,q;	
	cin >> n >> p >> q;
	gmin(p,n);
	gmin(q,n);
	vector<int> pos(n+1);
	for(int i = 1;i <= n; ++i){
		cin >> pos[i];	
	}
	sort(all(pos));
	int l = 1, r = 1e9, ans = inf;
	while(l <= r){
		int m = l + (r-l)/2;
		for(int i = 0;i <= n; ++i){
			for(int j = 0;j <= n; ++j){
				dp[i][j] = inf;
			}
		}
		dp[0][0] = 0;
		for(int i = 0;i < n; ++i){
			int nxts = (int)(upper_bound(all(pos), pos[i+1] + m - 1) - pos.begin()) - 1;	
			int nxtl = (int)(upper_bound(all(pos), pos[i+1] + 2*m - 1) - pos.begin()) - 1;	
			for(int j = 0;j <= n; ++j){
				gmin(dp[nxts][j+1], dp[i][j]);
				gmin(dp[nxtl][j], dp[i][j] + 1);
			}
		}
		int mn = inf;
		for(int i = 0;i <= p; ++i){
			gmin(mn, dp[n][i]);
		}
		if(mn <= q){
			ans = m;
			r = m - 1;
		}
		else{
			l = m + 1;
		}
	}
	cout << ans << '\n';
}

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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 4 ms 760 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Correct 4 ms 800 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 3 ms 760 KB Output is correct
15 Correct 3 ms 760 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 16220 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 317 ms 16120 KB Output is correct
4 Correct 321 ms 16248 KB Output is correct
5 Correct 319 ms 16120 KB Output is correct
6 Correct 316 ms 16120 KB Output is correct
7 Correct 318 ms 16120 KB Output is correct
8 Correct 323 ms 16124 KB Output is correct
9 Correct 329 ms 16112 KB Output is correct
10 Correct 326 ms 16220 KB Output is correct
11 Correct 327 ms 16248 KB Output is correct
12 Correct 326 ms 16120 KB Output is correct
13 Correct 318 ms 16112 KB Output is correct
14 Correct 318 ms 16148 KB Output is correct
15 Correct 348 ms 16120 KB Output is correct