oj.uz

Submission #98767

# Submission time Handle Problem Language Result Execution time Memory
98767 2019-02-25T17:13:11 Z figter001 Watching (JOI13_watching) C++14
100 / 100
 872 ms 16248 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll oo = 1e18;
const int mod = 1e9+7;
const int nax = 2020;

int n,s,b;
int dp[nax][nax];
vector<int> a;

bool can(int w){
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			dp[i][j] = 2e9;
	int to = -1,u = 0;
	for(int i=0;i<n;i++){
		if(a[i] > to){
			to = a[i] + w - 1;
			u++;
		}
		dp[i][0] = u;
	}
	int idx = 0,idx2=0;
	for(int i=0;i<n;i++){
		for(int j=1;j<=b;j++){
			int cur = a[i] - 2*w + 1,at;
			if(cur <= 0)dp[i][j] = 0;
			else{
				while(idx < n && cur > a[idx])
					idx++;
				at = idx;
				if(at == 0){
					dp[i][j] = 0;
				}else{
					at--;
					dp[i][j] = min(dp[i][j],dp[at][j-1]);
					// if(i)dp[i][j] = min(dp[i][j],dp[i-1][j]+1);
				}
			}
			cur = a[i] - w + 1;
			if(cur <= 0)dp[i][j] = 0;
			else{
				while(idx2 < n && cur > a[idx2])
					idx2++;
				at = idx2;
				if(at == 0){
					dp[i][j] = 0;
				}else{
					at--;
					dp[i][j] = min(dp[i][j],dp[at][j]+1);
					// if(i)dp[i][j] = min(dp[i][j],dp[i-1][j]+1);
				}
			}
		}
	}
	return dp[n-1][b] <= s;
}

int main(){
	cin>>n>>s>>b;
	s = min(s,n);
	b = min(b,n);
	a.resize(n);
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a.begin(),a.end());
	int md,lo=1,hi=1e9,ans = 0;
	while(lo <= hi){
		md = (lo + hi)/2;
		if(can(md)){
			ans = md;
			hi = md-1;
		}else lo = md+1;
	}
	cout << ans << endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 3 ms 768 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 16128 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 586 ms 16128 KB Output is correct
4 Correct 123 ms 16248 KB Output is correct
5 Correct 759 ms 16248 KB Output is correct
6 Correct 812 ms 16248 KB Output is correct
7 Correct 119 ms 16120 KB Output is correct
8 Correct 428 ms 16248 KB Output is correct
9 Correct 152 ms 16120 KB Output is correct
10 Correct 142 ms 16244 KB Output is correct
11 Correct 872 ms 16224 KB Output is correct
12 Correct 410 ms 16128 KB Output is correct
13 Correct 104 ms 16128 KB Output is correct
14 Correct 102 ms 16208 KB Output is correct
15 Correct 111 ms 16120 KB Output is correct