Submission #853616

#TimeUsernameProblemLanguageResultExecution timeMemory
853616mbfibatSure Bet (CEOI17_sure)C++17
100 / 100
63 ms1996 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 11;
double a[N], b[N];

int main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i] >> b[i];
	sort(a + 1, a + 1 + n, greater<double>());
	sort(b + 1, b + 1 + n, greater<double>());

	double ans = 0.0;

	int pos_a = 1, pos_b = 1, cnt = 0;
	double sum_a = 0, sum_b = 0;
	while (1) {
		++cnt;
		if (sum_a < sum_b) {	
			if (pos_a > n) break;
			sum_a += a[pos_a++];
		} else if (sum_b < sum_a) {
			if (pos_b > n) break;
			sum_b += b[pos_b++];
		} else {
			if (sum_a > n || sum_b > n) break;
			sum_a += a[pos_a++];
		}
		double val = min(sum_a - cnt, sum_b - cnt);
		ans = max(ans, val);
	}

	cout << setprecision(4) << fixed << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...