Submission #879271

#TimeUsernameProblemLanguageResultExecution timeMemory
879271vjudge1Sure Bet (CEOI17_sure)C++17
100 / 100
63 ms8516 KiB
#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

using ld = double;

const int N = 1e6 + 123;

ld a[N], b[N];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; ++ i) cin >> a[i] >> b[i];
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + n);
	reverse(a + 1, a + 1 + n);
	reverse(b + 1, b + 1 + n);
	for (int i = 1 ; i <= n ; ++ i) a[i] += a[i - 1], b[i] += b[i - 1];
	int l = 1, r = 1;
	ld ans = max(0.0, min(a[1], b[1]) - 2);
	while (l < n || r < n) {
		if (l == n || (r < n && min(a[l], b[r + 1]) >= min(a[l + 1], b[r]))) {
			++r;
		} else {
			++l;
		}
		ld cur = min(a[l], b[r]) - (l + r);
		ans = max(ans, cur);
	}
	cout << fixed << setprecision(4);
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...