Submission #571976

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
571976	2022-06-03T08:14:27 Z	1ne	Watching (JOI13_watching)	C++14	100 / 100	819 ms	30340 KB

watching

#include<bits/stdc++.h>
using namespace std;
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,p,q;cin>>n>>p>>q;
	vector<long long>arr(n);
	for (long long i = 0;i<n;++i)cin>>arr[i];
	sort(arr.begin(),arr.end());
	long long left = 1,right = 1e10;
	if (p + q >=n){
		cout<<1<<'\n';
		return 0;
	}
	long long ans = right;
	function<bool(long long)>check = [&](long long u){
		vector<vector<pair<int,int>>>adj(n);
		p = min(p,n);
		vector<vector<long long>>dp(n + 1,vector<long long>(p + 1,LLONG_MAX));
		dp[0][0] = 0;
		for (int i = 0;i<n;++i){
			long long nxt = lower_bound(arr.begin(),arr.end(),arr[i] + 2 * u - 1) - arr.begin();
			long long nxt2 = lower_bound(arr.begin(),arr.end(),arr[i] + u - 1) - arr.begin();
			while((nxt==n) || (arr[nxt] - arr[i] > 2 * u - 1))--nxt;
			while((nxt2==n) || (arr[nxt2] - arr[i] > u - 1))--nxt2;
			while(nxt + 1<n && arr[nxt + 1] - arr[i] <=2 * u - 1)++nxt;
			while(nxt2 + 1<n && arr[nxt2 + 1] - arr[i] <=u - 1)++nxt2;
			for (int j = 0;j<=p;++j){
				if (dp[i][j]==LLONG_MAX)continue;
				dp[min(n,nxt + 1)][j] = min(dp[i][j] + 1,dp[min(n,nxt + 1)][j]);
				if (j + 1<=p)
					dp[min(n,nxt2 + 1)][j + 1] = min(dp[i][j],dp[min(n,nxt2 + 1)][j + 1]);
			}
		}
		for (int i = 0;i<=p;++i){
			if (dp[n][i]<=q)return true;
		}
		return false;
	};
	while(left<=right){
		long long mid = (left + right)>>1;
		if (check(mid)){
			right = mid - 1;
			ans = mid;
		}
		else{
			left = mid + 1;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

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	324 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 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	316 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	468 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	9 ms	596 KB	Output is correct
8	Correct	59 ms	2440 KB	Output is correct
9	Correct	325 ms	12336 KB	Output is correct
10	Correct	819 ms	30340 KB	Output is correct
11	Correct	55 ms	1908 KB	Output is correct
12	Correct	459 ms	15860 KB	Output is correct
13	Correct	9 ms	596 KB	Output is correct
14	Correct	17 ms	756 KB	Output is correct
15	Correct	17 ms	732 KB	Output is correct