Submission #170344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
170344	2019-12-24T20:17:46 Z	ngmh	Watching (JOI13_watching)	C++11	50 / 100	1000 ms	31996 KB

watching

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-