Submission #97286

#	Time	Username	Problem	Language	Result	Execution time	Memory
97286		dalgerok	Sure Bet (CEOI17_sure)	C++14	100 / 100	133 ms	3832 KiB

sure

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



const int N = 1e5 + 5;



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



int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        a[i] -= 1;
        b[i] -= 1;
    }
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    reverse(b + 1, b + n + 1);
    double ans = 0, sum_a = 0, sum_b = 0;
    for(int na = 0, nb = 0; na <= n; na++){
        if(na){
            sum_a += a[na];
        }
        while(nb + 1 <= n && min(sum_a - nb, sum_b - na) < min(sum_a - (nb + 1), sum_b + a[nb + 1] - na)){
            sum_b += b[nb + 1];
            nb += 1;
        }
        //cout << sum_a << " " << sum_b << " " << na << " " << nb << "\n";
        ans = max(ans, min(sum_a - nb, sum_b - na));
    }
    cout << fixed << setprecision(4) << ans;
}

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