Submission #930664

#	Time	Username	Problem	Language	Result	Execution time	Memory
930664		oblantis	Sure Bet (CEOI17_sure)	C++17	100 / 100	68 ms	5208 KiB

sure

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e6 + 1;

void solve() {
	int n;
	cin >> n;
	double a[n], b[n], a0[n], b0[n], ans = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
	}
	sort(a, a + n), sort(b, b + n);
	for(int i = 0; i < n; i++){
		a0[i] = a[i] - 2;
		b0[i] = b[i] - 2;
		a[i]--, b[i]--;
		if(i)a[i] += a[i - 1], b[i] += b[i - 1];
	}
	double s = 0, t = 0;
	for(int i = n - 1; i >= 0; i--){
		s += a0[i], t += b0[i];
		ans = max(ans, min(s, t));
		int l = -1, r = i;
		if(s < t){
			while(l + 1 < r){
				int mid = l + (r - l) / 2;
				if(t - (i - mid) > s + (i ? a[i - 1] : 0) - (mid ? a[mid - 1] : 0))r = mid;
				else l = mid;
			}
			ans = max(ans, s + (i ? a[i - 1] : 0) - (r ? a[r - 1] : 0));
			if(r)ans = max(ans, t - (i - r) - 1);
		}
		else if(s > t){
			while(l + 1 < r){
				int mid = l + (r - l) / 2;
				if(s - (i - mid) > t + (i ? b[i - 1] : 0) - (mid ? b[mid - 1] : 0))r = mid;
				else l = mid;
			}
			ans = max(ans, t + (i ? b[i - 1] : 0) - (r ? b[r - 1] : 0));
			if(r){
				ans = max(ans, s - (i - r) - 1);
			}
		}
	}
	cout << fixed << setprecision(4) << ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

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