Submission #571978

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
571978	2022-06-03T08:15:34 Z	1ne	Watching (JOI13_watching)	C++14	100 / 100	686 ms	30380 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) - arr.begin();
			long long nxt2 = lower_bound(arr.begin(),arr.end(),arr[i] + u) - arr.begin();
			for (int j = 0;j<=p;++j){
				if (dp[i][j]==LLONG_MAX)continue;
				dp[nxt][j] = min(dp[i][j] + 1,dp[nxt][j]);
				if (j + 1<=p)
					dp[nxt2][j + 1] = min(dp[i][j],dp[nxt2][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	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 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	340 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	6 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	340 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	8 ms	596 KB	Output is correct
8	Correct	51 ms	2436 KB	Output is correct
9	Correct	265 ms	12408 KB	Output is correct
10	Correct	686 ms	30380 KB	Output is correct
11	Correct	40 ms	1932 KB	Output is correct
12	Correct	389 ms	15860 KB	Output is correct
13	Correct	8 ms	596 KB	Output is correct
14	Correct	11 ms	740 KB	Output is correct
15	Correct	10 ms	708 KB	Output is correct