제출 #97286

#제출 시각아이디문제언어결과실행 시간메모리
97286dalgerokSure Bet (CEOI17_sure)C++14
100 / 100
133 ms3832 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...