Submission #115204

#	Time	Username	Problem	Language	Result	Execution time	Memory
115204		minhtung0404	Sure Bet (CEOI17_sure)	C++17	100 / 100	127 ms	3704 KiB

sure

//https://csacademy.com/contest/ceoi-2017-day-1/task/sure-bet/

#include<bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;

int n;
double a[N], b[N], ans;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    sort(a+1, a+1+n, greater <double> ()); sort(b+1, b+1+n, greater <double> ());
    for (int i = 1; i <= n; i++) a[i] += a[i-1], b[i] += b[i-1];
    for (int i = 1; i <= 2*n; i++){
        int l = max(i-n, 0), r = min(n, i);
        while (l != r){
            int mid = (l + r) >> 1;
            if (a[mid] >= b[i-mid]) r = mid;
            else l = mid+1;
        }
        ans = max(ans, min(a[l], b[i-l]) - i);
        if (l > 0 && i-l < n) ans = max(ans, min(a[l-1], b[i-l+1]) - i);
    }
    cout << fixed << setprecision(4) << ans;
}

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