Submission #1191720

#TimeUsernameProblemLanguageResultExecution timeMemory
1191720petezaSure Bet (CEOI17_sure)C++20
100 / 100
46 ms1864 KiB
#include <bits/stdc++.h>
using namespace std;
using db = double;

int n;
db qsa[100005], qsb[100005];
db ans = 0;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> qsa[i] >> qsb[i];
    sort(qsa+1, qsa+n+1); sort(qsb+1, qsb+n+1);
    reverse(qsa+1, qsa+n+1); reverse(qsb+1, qsb+n+1);
    for(int i=1;i<=n;i++) {
        qsa[i] += qsa[i-1];
        qsb[i] += qsb[i-1];
    }
    int p1 = 0;
    for(int i=1;i<=n;i++) {
        while(p1 <= n && qsb[p1] <= qsa[i]) p1++;
        if(p1 <= n) ans = max(ans, qsa[i] - i - p1);
        ans = max(ans, qsb[p1-1] - i - (p1 - 1));
        //cout << i << ' ' << p1 << " -> " << ans << '\n';
    }
    cout << fixed << setprecision(4) << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...