oj.uz

답안 #41022

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
41022 2018-02-11T23:46:48 Z IvanC 구경하기 (JOI13_watching) C++14
100 / 100
 852 ms 33008 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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