Submission #41022

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
41022	2018-02-11T23:46:48 Z	IvanC	Watching (JOI13_watching)	C++14	100 / 100	852 ms	33008 KB

watching

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2010;
vector<ll> V;
ll dp[MAXN][MAXN],nxt[MAXN][2],N,P,Q,W;
ll solve(ll pos,ll resta){
	if(dp[pos][resta] != -1) return dp[pos][resta];
	if(pos == N) return 0;
	ll best = 1 + solve(nxt[pos][0]+1,resta);
	if(resta != 0) best = min(best, solve(nxt[pos][1] + 1,resta - 1) );
	return dp[pos][resta] = best;
}
ll check(ll val){
	W = val;
	memset(dp,-1,sizeof(dp));
	for(ll i = 0;i<N;i++){
		nxt[i][0] = prev(upper_bound(V.begin(),V.end(),V[i] + W - 1)) - V.begin();
		nxt[i][1] = prev(upper_bound(V.begin(),V.end(),V[i] + 2*W - 1)) - V.begin();
	}
	return solve(0,Q) <= P;
}
int main(){
	cin >> N >> P >> Q;
	for(ll i = 0;i<N;i++){
		ll x;
		cin >> x;
		V.push_back(x);
	}
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
	N = V.size();
	P = min(P,N);
	Q = min(Q,N);
	ll ini = 1,fim = (ll)1e9,meio,resp = -1;
	while(ini <= fim){
		meio = ini + (fim - ini)/2;
		if(check(meio)){
			resp = meio;
			fim = meio - 1;
		}
		else{
			ini = meio + 1;
		}
	}
	cout << resp << endl;
	return 0;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	202 ms	32084 KB	Output is correct
2	Correct	205 ms	32084 KB	Output is correct
3	Correct	208 ms	32216 KB	Output is correct
4	Correct	198 ms	32216 KB	Output is correct
5	Correct	200 ms	32216 KB	Output is correct
6	Correct	215 ms	32216 KB	Output is correct
7	Correct	207 ms	32300 KB	Output is correct
8	Correct	205 ms	32348 KB	Output is correct
9	Correct	208 ms	32356 KB	Output is correct
10	Correct	199 ms	32360 KB	Output is correct
11	Correct	222 ms	32360 KB	Output is correct
12	Correct	220 ms	32360 KB	Output is correct
13	Correct	209 ms	32368 KB	Output is correct
14	Correct	192 ms	32368 KB	Output is correct
15	Correct	195 ms	32380 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	217 ms	32548 KB	Output is correct
2	Correct	190 ms	32548 KB	Output is correct
3	Correct	617 ms	32632 KB	Output is correct
4	Correct	226 ms	32632 KB	Output is correct
5	Correct	722 ms	32856 KB	Output is correct
6	Correct	712 ms	32856 KB	Output is correct
7	Correct	209 ms	32856 KB	Output is correct
8	Correct	382 ms	32856 KB	Output is correct
9	Correct	254 ms	32856 KB	Output is correct
10	Correct	255 ms	32880 KB	Output is correct
11	Correct	852 ms	32880 KB	Output is correct
12	Correct	622 ms	33008 KB	Output is correct
13	Correct	210 ms	33008 KB	Output is correct
14	Correct	202 ms	33008 KB	Output is correct
15	Correct	209 ms	33008 KB	Output is correct