Submission #1221743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221743		radodododo	Sure Bet (CEOI17_sure)	C++20	100 / 100	51 ms	2784 KiB

sure

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long n;
	cin >> n;
	vector<double> a(n), b(n);
	for (long long i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		a[i] -= 1;
		b[i] -= 1;
	}
	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	sort(b.begin(), b.end());
	reverse(b.begin(), b.end());
	double ans = 0;
	vector<double> prefb(n);
	prefb[0] = b[0];
	for (long long i = 1; i < n; i++) {
		prefb[i] = prefb[i - 1] + b[i];
	}
	double sum = 0;
	for (long long i = 0; i < n; i++) {
		sum += a[i];
		double ansi = sum + i + 1;
		long long l = 0, r = n - 1;
		while (l != r) {
			long long mid = (l + r + 1) / 2;
			double ansmid = prefb[mid] + mid + 1;
			if (ansmid < ansi) {
				l = mid;
			}
			else {
				r = mid - 1;
			}
		}
		ans = max(ans, min(sum - l - 1, prefb[l] - i - 1));
		if (l != n - 1) {
			l++;
		}
		ans = max(ans, min(sum - l - 1, prefb[l] - i - 1));
	}
	printf("%.4lf", (double)ans);
}

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