Submission #320679

#	Time	Username	Problem	Language	Result	Execution time	Memory
320679		phathnv	Sure Bet (CEOI17_sure)	C++11	100 / 100	111 ms	4588 KiB

sure

#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;
}

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