oj.uz

답안 #170344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170344 2019-12-24T20:17:46 Z ngmh 구경하기 (JOI13_watching) C++11
50 / 100
 1000 ms 31996 KB 
#include <bits/stdc++.h>
using namespace std;

long long n, p, q, a[2005], mini, medi, maxi, far, dp[2005][2005];

long long need(long long idx, long long big, long long w){
	if(idx < 0) return 0;
	if(dp[idx][big] != -1) return dp[idx][big];
	dp[idx][big] = INT_MAX;
	if(big > 0){
		far = upper_bound(a, a+n, a[idx]-w-w)-a;
		far--;
		dp[idx][big] = min(dp[idx][big], need(far, big-1, w));
	}
	far = upper_bound(a, a+n, a[idx]-w)-a;
	far--;
	dp[idx][big] = min(dp[idx][big], (long long) (need(far, big, w)+1));
	return dp[idx][big];
}

int main(){
	cin >> n >> p >> q;
	if(p+q >= n){
		cout << 1;
		return 0;
	}
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a+n);
	mini = 0; maxi = a[n-1]+1;
	while(mini < maxi){
		medi = mini+(maxi-mini)/2;
		memset(dp, -1, sizeof(dp));
		if(need(n-1, q, medi) <= p) maxi = medi;
		else mini = medi+1;
	}
	cout << mini;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 31864 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 137 ms 31804 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 120 ms 31864 KB Output is correct
8 Correct 140 ms 31736 KB Output is correct
9 Correct 141 ms 31736 KB Output is correct
10 Correct 161 ms 31832 KB Output is correct
11 Correct 163 ms 31828 KB Output is correct
12 Correct 149 ms 31864 KB Output is correct
13 Correct 138 ms 31736 KB Output is correct
14 Correct 112 ms 31736 KB Output is correct
15 Correct 171 ms 31864 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 31860 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 197 ms 31892 KB Output is correct
8 Execution timed out 1068 ms 31996 KB Time limit exceeded
9 Halted 0 ms 0 KB -