Submission #305135

#	Time	Username	Problem	Language	Result	Execution time	Memory
305135		miss_robot	Sure Bet (CEOI17_sure)	C++14	100 / 100	118 ms	4472 KiB

sure

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;

double f(int x, int y, vector<double>& a, vector<double>& b){
	return min(a[x], b[y])-x-y;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << setprecision(4) << fixed;
	int n;
	double sol = 0;
	cin >> n;
	vector<double> a(n), b(n);
	for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
	sort(a.rbegin(), a.rend());
	sort(b.rbegin(), b.rend());
	a.insert(a.begin(), 0);
	b.insert(b.begin(), 0);
	for(int i = 1; i <= n; i++) a[i] += a[i-1], b[i] += b[i-1];
	for(int i = 0; i <= n; i++){
		int l = 0, h = n, m;
		while(l < h){
			if(l == h-1){
				if(f(i, l, a, b) > f(i, h, a, b)) h--;
				else l++;
			}
			else{
				m = (l+h)/2;
				if(f(i, m, a, b) >= f(i, m+1, a, b)) h = m;
				else l = m+1;
			}
		}
		sol = max(sol, f(i, l, a, b));
	}
	cout << sol << "\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40