Submission #865491

#	Time	Username	Problem	Language	Result	Execution time	Memory
865491		vjudge1	Sure Bet (CEOI17_sure)	C++98	100 / 100	70 ms	5976 KiB

sure

#include <bits/stdc++.h>
#include <sstream>
#include <fstream>
#define et "\n"
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define ioi ios::sync_with_stdio(false); cin.tie(0);  cout.tie(0)
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define M 1000000007
 
using namespace std;
ll n,m,k;

string s1;
map <ll,ll> mp;
double ans,cnt,cnt1;
double a[211111],b[211111],c[211111],c1 = 0;
void solve() {
	cin >> n;
	ans = 0;
	for (int i = 1;i <= n;i++) {
		cin >> a[i] >> b[i];
		a[i] = -a[i];
		b[i] = -b[i];
	}
	sort(a + 1,a + n + 1);
	sort(b + 1,b + n + 1);
	for (int i = 1;i <= n;i++) {
		a[i] = -a[i];
		b[i] = -b[i]; 
	}
	for (int i = 1;i <= n;i++) {
		c[i] = b[i] + c[i - 1];
	}
	cnt = 0;
	cnt1 = 0;
	for (int i = 1;i <= n;i ++) {
		c1 = i;
		cnt += a[i];
		ll l = 1,r = n;
		while (l <= r) {
			ll tm = (l + r) >> 1;
//			cout << ans << ' ' << l << ' ' << r << ' ' << a[i] << ' ' << cnt << ' ' << c[tm] << et;
			ans = max(ans,min(c[tm] - c1 - tm,cnt - c1 - tm));
			if (cnt > c[tm]) {
				if (b[tm] > 1) {
					l = tm + 1;
				}
				else {
					r = tm - 1;
				}
			}
			else {
				r = tm - 1;
			}
			
		}
	}
	printf("%.4lf",(double)ans);
}
int main() {
	ioi;
	ll tt = 1;
//	cin >> tt;
	while (tt--) {
		solve();
	}
}

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