Submission #320679

#TimeUsernameProblemLanguageResultExecution timeMemory
320679phathnvSure Bet (CEOI17_sure)C++11
100 / 100
111 ms4588 KiB
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const double INF = 1e9;

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

void readInput(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
}

void prepare(){
    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];
    }
}

void calc(int l, int r, int from, int to){
    if (l > r)
        return;
    int mid = (l + r) >> 1;
    int pos = -1;
    dp[mid] = -INF;
    for(int i = from; i <= to; i++)
        if (dp[mid] < min(a[mid], b[i]) - (mid + i)){
            dp[mid] = min(a[mid], b[i]) - (mid + i);
            pos = i;
        }
    calc(l, mid - 1, from, pos);
    calc(mid + 1, r, pos, to);
}

void solve(){
    calc(1, n, 0, n);
    cout << fixed << setprecision(4) << *max_element(dp, dp + 1 + n);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    readInput();
    prepare();
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...