oj.uz

Submission #521376

# Submission time Handle Problem Language Result Execution time Memory
521376 2022-02-02T02:12:18 Z amunduzbaev Watching (JOI13_watching) C++14
100 / 100
 366 ms 16196 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 2e3 + 5;
int a[N], n, p, q;
int dp[N][N], pw[N], p2w[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>p>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} sort(a + 1, a + n + 1);
	p = min(p, n), q = min(q, n);
	
	auto check = [&](int w){
		memset(dp, 127, sizeof dp);
		memset(pw, -1, sizeof pw);
		memset(p2w, -1, sizeof p2w);
		for(int i=1;i<=n;i++){
			for(int j=i-1;j>0;j--){
				if(a[i] - a[j] + 1 > w && pw[i] == -1) pw[i] = j;
				if(a[i] - a[j] + 1 > 2 * w && p2w[i] == -1) p2w[i] = j;
			} if(pw[i] == -1) pw[i] = 0;
			if(p2w[i] == -1) p2w[i] = 0;
		}
		
		for(int i=0;i<N;i++) dp[0][i] = 0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=n;j++){
				if(j > 0) dp[i][j] = min(dp[i][j], dp[pw[i]][j - 1]);
				dp[i][j] = min(dp[i][j], dp[p2w[i]][j] + 1);
			}
		}
		
		return (dp[n][p] <= q);
	};
	
	int l = 1, r = 1e9;
	while(l < r){
		int m = (l + r) >> 1;
		if(check(m)) r = m;
		else l = m + 1;
	}
	
	//~ cout<<check(l)<<" ";
	cout<<l<<"\n";
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 16044 KB Output is correct
2 Correct 56 ms 15948 KB Output is correct
3 Correct 55 ms 15948 KB Output is correct
4 Correct 55 ms 16044 KB Output is correct
5 Correct 55 ms 16048 KB Output is correct
6 Correct 55 ms 16048 KB Output is correct
7 Correct 54 ms 16056 KB Output is correct
8 Correct 54 ms 16064 KB Output is correct
9 Correct 54 ms 15948 KB Output is correct
10 Correct 55 ms 16044 KB Output is correct
11 Correct 62 ms 16048 KB Output is correct
12 Correct 56 ms 15948 KB Output is correct
13 Correct 53 ms 15948 KB Output is correct
14 Correct 55 ms 16044 KB Output is correct
15 Correct 59 ms 16044 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 16052 KB Output is correct
2 Correct 55 ms 16044 KB Output is correct
3 Correct 324 ms 16056 KB Output is correct
4 Correct 314 ms 16056 KB Output is correct
5 Correct 311 ms 16056 KB Output is correct
6 Correct 322 ms 16068 KB Output is correct
7 Correct 336 ms 16056 KB Output is correct
8 Correct 315 ms 16052 KB Output is correct
9 Correct 317 ms 16052 KB Output is correct
10 Correct 318 ms 16068 KB Output is correct
11 Correct 306 ms 16076 KB Output is correct
12 Correct 314 ms 16076 KB Output is correct
13 Correct 366 ms 16088 KB Output is correct
14 Correct 364 ms 16076 KB Output is correct
15 Correct 324 ms 16196 KB Output is correct