Submission #248987

#TimeUsernameProblemLanguageResultExecution timeMemory
248987SortingSure Bet (CEOI17_sure)C++14
100 / 100
110 ms3704 KiB
#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e5 + 3;

double a[k_N], b[k_N];

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

    int n;
    cin >> n;

    for(int i = 0; i < n; ++i)
        cin >> a[i] >> b[i];

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

    double curr_a = 0, curr_b = 0, answer = 0;
    int i = 0, j = 0;
    while(i != n && j != n){
        if(curr_a < curr_b)
            curr_a += a[i], i++;
        else
            curr_b += b[j], j++;
        answer = max(min(curr_a, curr_b) - i - j, answer);
    }

    while(i != n){
        curr_a += a[i], i++;
        answer = max(min(curr_a, curr_b) - i - j, answer);
    }

    while(j != n){
        curr_b += b[j], j++;
        answer = max(min(curr_a, curr_b) - i - j, answer);
    }

    cout << fixed << setprecision(4) << answer << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...