Submission #595874

#	Time	Username	Problem	Language	Result	Execution time	Memory
595874		OttoTheDino	Sure Bet (CEOI17_sure)	C++17	100 / 100	62 ms	3604 KiB

sure

#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                      for (int i = s; i <= e; ++i)
#define len(a)                          (int)a.size()
typedef long long ll;

const ll C = 1e4;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    ll a[n+1] = {}, b[n+1] = {};

    rep (i,0,n-1) {
        string sx, sy; cin >> sx >> sy;
        ll x = 0, y = 0, idx = 0, idy = 0;
        rep (j,0,len(sx)-1) {
            if (sx[j]=='.') idx = j;
            else {
                x *= 10;
                x += (sx[j]-'0');
            }
        }
        rep (j,0,len(sy)-1) {
            if (sy[j]=='.') idy = j;
            else {
                y *= 10;
                y += (sy[j]-'0');
            }
        }
        if (!idx) idx = len(sx)-1;
        if (!idy) idy = len(sy)-1;
        x *= pow(10, 4-len(sx)+1+idx);  
        y *= pow(10, 4-len(sy)+1+idy);
        a[i] = x;
        b[i] = y; 
    }

    sort (a, a+n, greater<ll>());
    sort (b, b+n, greater<ll>());

    ll lo = 0, hi = 1e13;

    while (lo<hi) {
        ll mid = (lo+hi+1)/2, id = 0, s1 = 0, s2 = 0, suc = 0;
        rep (i,0,n) {
            if (min(s1,s2)-C*(i+id)>=mid) {
                suc = 1;
                break;
            }
            s1 += a[i];
            while (id < n && s2-C*(i+1+id)<mid) {
                s2 +=b[id];
                ++id;
            }
        }
        if (suc) lo = mid;
        else hi = mid-1;
    }

    cout << fixed << setprecision(4) << (double)lo/C << "\n";

    return 0;
}

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