Submission #1119378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119378		South_Cloud	Sure Bet (CEOI17_sure)	C++17	0 / 100	1 ms	336 KiB

sure

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const int N = 1e5;

int n;

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

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

void solve() {
    sort(a[0] + 1, a[0] + n + 1, greater<double>());
    sort(a[1] + 1, a[1] + n + 1, greater<double>());
//    for(int i = 1; i <= n; i++) cout << a[0][i] << " ";
//    cout << '\n';
//    for(int i = 1; i <= n; i++) cout << a[1][i] << " ";
//    cout << '\n';
    for(int i = 1; i <= n; i++) {
        pref[0][i] = pref[0][i - 1] + a[0][i];
        pref[1][i] = pref[1][i - 1] + a[1][i];
    }
    for(int x = 0; x <= 1; x++) {
        double cur = 0;
        int cnt = 0;
        for(int i = 1; i <= n; i++) {
            cnt++;
            cur += a[x][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[x ^ 1][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