제출 #1221739

#제출 시각아이디문제언어결과실행 시간메모리
1221739radodododoSure Bet (CEOI17_sure)C++20
0 / 100
0 ms320 KiB
#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<long 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());
	long double ans = 0;
	vector<long double> prefb(n);
	prefb[0] = b[0];
	for (long long i = 1; i < n; i++) {
		prefb[i] = prefb[i - 1] + b[i];
	}
	long double sum = 0;
	for (long long i = 0; i < n; i++) {
		sum += a[i];
		long double ansi = sum + i + 1;
		long long l = 0, r = n - 1;
		while (l != r) {
			long long mid = (l + r + 1) / 2;
			long 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));
	}
	cout.precision(20);
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...