Submission #573502

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
573502	2022-06-06T18:13:51 Z	dsyz	Watching (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

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

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