답안 #573502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573502	2022-06-06T18:13:51 Z	dsyz	구경하기 (JOI13_watching)	C++17	100 / 100	294 ms	31656 KB

watching

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (2005)
ll N,P,Q;
ll arr[MAXN];
bool bs(ll w){
	ll dp[N][P + 1]; //number of events covered, number of small cameras, value: number of big cameras needed
	memset(dp,0,sizeof(dp));
	for(ll i = N - 1;i >= 0;i--){
		ll y = lower_bound(arr,arr + N,arr[i] + 2 * w) - arr;
		ll x = lower_bound(arr,arr + N,arr[i] + w) - arr;
		if (y == N) dp[i][0] = 1;
		else dp[i][0] = dp[y][0] + 1;
		for(ll j = 1;j <= P;j++) {
			if (y == N) dp[i][j] = 1;
			else dp[i][j] = dp[y][j] + 1;
			if (x == N) dp[i][j] = 0;
			else dp[i][j] = min(dp[i][j], dp[x][j - 1]);
		}
	}
	return dp[0][P] <= Q;
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>P>>Q;
	P = min(P,N);
	Q = min(Q,N);
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	sort(arr,arr + N);
	ll low = 0;
	ll high = 1000000000;
	while(high - low > 1){
		ll mid = (high + low) / 2;
		if(bs(mid)){
			high = mid;
		}else{
			low = mid;
		}
	}
	cout<<high<<'\n';
}

Subtask #1

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	328 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	324 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	324 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	332 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	231 ms	23828 KB	Output is correct
4	Correct	294 ms	31576 KB	Output is correct
5	Correct	12 ms	1492 KB	Output is correct
6	Correct	279 ms	31656 KB	Output is correct
7	Correct	5 ms	468 KB	Output is correct
8	Correct	18 ms	2308 KB	Output is correct
9	Correct	104 ms	12140 KB	Output is correct
10	Correct	273 ms	30032 KB	Output is correct
11	Correct	14 ms	1748 KB	Output is correct
12	Correct	143 ms	15700 KB	Output is correct
13	Correct	6 ms	468 KB	Output is correct
14	Correct	9 ms	596 KB	Output is correct
15	Correct	9 ms	596 KB	Output is correct