Submission #1119373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119373		vjudge1	Sure Bet (CEOI17_sure)	C++17	0 / 100	1 ms	340 KiB

sure

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const int N = 1e5;

int n;

double a[N + 2], b[N + 2], pref[N + 2], ans = 0;

void input() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
}

void solve() {
    sort(a + 1, a + n + 1, greater<double>());
    sort(b + 1, b + n + 1, greater<double>());
//    for(int i = 1; i <= n; i++) cout << a[i] << " ";
//    cout << '\n';
//    for(int i = 1; i <= n; i++) cout << b[i] << " ";
//    cout << '\n';
    for(int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + b[i];
    }
    double cur = 0;
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        cnt++;
        cur += a[i];
        if(cur - cnt < 0) continue;
        int l = 0, r = n;
        while(r - l > 1) {
            int mid = (l + r) >> 1;
            int cost = cnt + mid;
            if(cur - cost < 0) r = mid;
                else {
                    if(cur - cost <= pref[mid] - cost) {
                        l = mid;
                    } else r = mid;
                }
        }
//        cout << i << " " << l << '\n';
        if(l > 0) ans = max(ans, cur - cnt - l);
    }
    cout << fixed << setprecision(4) << ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(" .inp", "r", stdin);
    //freopen(" .out", "w", stdout);
    input();
    solve();
    return 0;
}

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