답안 #379552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379552	2021-03-18T14:37:55 Z	penguin133	구경하기 (JOI13_watching)	C++14	100 / 100	250 ms	16236 KB

watching

#include <bits/stdc++.h>
using namespace std;
int n,p,q,s = 1, e= 1e9 + 5, ans = 1e9 + 5;
int dp[2005][2005], A[2005];
bool c(int x){
	for(int i=1;i<=n;i++){
		int l = 1, r = 1;
		while(A[i] - A[l] >= x)l++;
		while(A[i] - A[r] >= 2*x)r++;
		for(int j=0;j<=p;j++){
			if(j == 0)dp[i][j] = dp[r-1][j] + 1;
			else dp[i][j] = min(dp[l-1][j-1], dp[r-1][j] + 1);
		}
	}
	return dp[n][p] <= q;
}
int main(){
	cin >> n >> p >> q;
	for(int i=1;i<=n;i++)cin >> A[i];
	if(p + q >= n){
		cout << 1;
		exit(0);
	}
	sort(A+1, A+n+1);
	while(s <= e){
		int m = (s + e)/2;
		memset(dp, 0, sizeof(dp));
		if(c(m)){
			ans = m;
			e = m - 1;
		}
		else s = m + 1;
	}
	cout << ans;
}

Subtask #1

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	16236 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	69 ms	16108 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	70 ms	16108 KB	Output is correct
8	Correct	67 ms	16108 KB	Output is correct
9	Correct	68 ms	16108 KB	Output is correct
10	Correct	67 ms	16108 KB	Output is correct
11	Correct	69 ms	16108 KB	Output is correct
12	Correct	69 ms	16108 KB	Output is correct
13	Correct	69 ms	16108 KB	Output is correct
14	Correct	66 ms	16108 KB	Output is correct
15	Correct	67 ms	16108 KB	Output is correct

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	16108 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	118 ms	16108 KB	Output is correct
8	Correct	150 ms	16108 KB	Output is correct
9	Correct	180 ms	16108 KB	Output is correct
10	Correct	250 ms	16108 KB	Output is correct
11	Correct	133 ms	16236 KB	Output is correct
12	Correct	195 ms	16128 KB	Output is correct
13	Correct	112 ms	16236 KB	Output is correct
14	Correct	118 ms	16108 KB	Output is correct
15	Correct	118 ms	16108 KB	Output is correct