Submission #1111106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111106		Icelast	Sure Bet (CEOI17_sure)	C++17	100 / 100	404 ms	5212 KiB

sure

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
const double eps = 1e-6;
void solve(){
    int n;
    cin >> n;
    vector<double> a(n+1), b(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    sort(a.begin()+1, a.end(), greater<double>());
    sort(b.begin()+1, b.end(), greater<double>());
    vector<double> pfa(n+2, 0), pfb(n+2, 0);
    for(int i = 1; i <= n; i++){
        pfa[i] = pfa[i-1]+a[i];
        pfb[i] = pfb[i-1]+b[i];
    }
    pfa[n+1] = pfb[n+1] = INF;
    double ans = 0;
    auto cmp = [&](double a, double b) -> bool{
        return b-a > eps;
    };
    auto check = [&](double x, int k) -> bool{
        int pa = lower_bound(pfa.begin()+1, pfa.end(), x) - pfa.begin();
        if(pa == n+1) return false;
        int pb = lower_bound(pfb.begin()+1, pfb.end(), x) - pfb.begin();
        if(pb == n+1) return false;
        return pa+pb <= k;
    };
    for(int i = 1; i <= 2*n; i++){
        double l = 0, r = 1e9;
        while(r-l > eps){
            double mid = (l+r)/2;
            if(check(mid, i)){
                l = mid;
            }else{
                r = mid;
            }
        }
        ans = max(ans, l-i);
    }
    cout << fixed << setprecision(4) << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message (stderr)

sure.cpp: In function 'void solve()':
sure.cpp:23:10: warning: variable 'cmp' set but not used [-Wunused-but-set-variable]
   23 |     auto cmp = [&](double a, double b) -> bool{
      |          ^~~

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