Submission #958617

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
958617	2024-04-06T07:23:02 Z	pcc	Watching (JOI13_watching)	C++17	100 / 100	169 ms	16472 KB

watching

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2020;
int dp[mxn][mxn];
int N;
int arr[mxn];
int pt1,pt2;
int P,Q;

bool check(int len){
	pt1 = 0,pt2 = 0;
	for(int i = 1;i<=N;i++){
		while(arr[i]-arr[pt1]>=len)pt1++;
		while(arr[i]-arr[pt2]>=len*2)pt2++;
		for(int j = 0;j<=N;j++){
			dp[i][j] = 1e9;
			if(j)dp[i][j] = min(dp[i][j],dp[pt2-1][j-1]);
			dp[i][j] = min(dp[i][j],dp[pt1-1][j]+1);
		}
	}
	return dp[N][Q]<=P;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>P>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	if(P+Q>=N){
		cout<<1;
		return 0;
	}
	arr[0] = -1e9-10;
	sort(arr+1,arr+N+1);
	int l = 0,r = 1e9;
	while(l != r){
		int mid = (l+r)>>1;
		if(check(mid))r = mid;
		else l = mid+1;
	}
	cout<<l<<'\n';
	return 0;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	464 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	2620 KB	Output is correct
8	Correct	2 ms	2392 KB	Output is correct
9	Correct	2 ms	2392 KB	Output is correct
10	Correct	2 ms	2392 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	16280 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	496 KB	Output is correct
7	Correct	169 ms	16220 KB	Output is correct
8	Correct	159 ms	16220 KB	Output is correct
9	Correct	158 ms	16216 KB	Output is correct
10	Correct	155 ms	16220 KB	Output is correct
11	Correct	159 ms	16472 KB	Output is correct
12	Correct	156 ms	16280 KB	Output is correct
13	Correct	155 ms	16220 KB	Output is correct
14	Correct	163 ms	16360 KB	Output is correct
15	Correct	155 ms	16216 KB	Output is correct