oj.uz

Submission #571837

# Submission time Handle Problem Language Result Execution time Memory
571837 2022-06-02T20:47:19 Z 1ne Watching (JOI13_watching) C++14
0 / 100
 3 ms 388 KB 
#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 = 1e9;
	long long ans = right;
	function<bool(long long)>check = [&](long long u){
		long long cur = 0;
		long long sum = arr[0];
		long long big = q,small = p;
		while(cur < n){
			long long nxt = lower_bound(arr.begin(),arr.end(),sum + 2 * u - 1) - arr.begin();
			long long nxt2 = lower_bound(arr.begin(),arr.end(),sum + u - 1) - arr.begin();
			while(nxt!=n && arr[nxt] - sum > 2 * u - 1)--nxt;
			while(nxt2!=n && arr[nxt2] - sum > u - 1)--nxt2;
			while(nxt + 1<n && arr[nxt + 1] - sum <=2 * u - 1)++nxt;
			while(nxt2 + 1<n && arr[nxt2 + 1] - sum <=u - 1)++nxt2;
			if (nxt - cur >= 1 && (nxt - cur + 1)  >  (nxt2 - cur + 1) && big){
				--big;
				cur = nxt + 1;
				sum = arr[cur];
			}
			else if (nxt2 - cur >= 1 && small){
				--small;
				cur = nxt2 + 1;
				sum = arr[cur];
			}
			else if (nxt - cur >= 1 && big){
				--big;
				cur = nxt + 1;
				sum = arr[cur];
			}
			else if (small){
				cur = cur + 1;
				small--;
				sum = arr[cur];
			}
			else if (big){
				cur = cur + 1;
				big--;
				sum = arr[cur];
			}
			else break;
		}
		return (cur >= n);
	};
	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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 228 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 388 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -