Submission #501200

#	Time	Username	Problem	Language	Result	Execution time	Memory
501200		radal	Sure Bet (CEOI17_sure)	C++14	100 / 100	358 ms	8308 KiB

sure

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
const long long int N = 1e5+20,mod = 1e9+7,inf = 1e9+10,sq = 400;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,int k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
ld a[N],b[N];
ld suf[N][2];
int n;
inline ld check(int i){
    if (i > n || i < 0) return 0;
    ld ans = min(suf[n-i][0]-i,ld(0));
    rep(j,1,n+1){
        ans = max(ans,min(suf[n-i][0],suf[n-j][1])-i-j);
    }
    return ans;
}
inline ld ternery(){
    int l = 0,r = n,m1 = 9,m2 = 0;
    while (r-l > 2){
        m1 = (2*l+r)/3;
        m2 = (l+2*r)/3;
        if (check(m1) < check(m2)) l = m1;
        else r = m2;
    }
    ld ans = max(check(0),check(n));
    rep(i,-300,300) ans = max(check(l+i),ans);
    return ans;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    rep(i,0,n){
        cin >> a[i] >> b[i];
    }
    sort(a,a+n);
    sort(b,b+n);
    repr(i,n-1,0){
        suf[i][0] = suf[i+1][0]+a[i];
        suf[i][1] = suf[i+1][1]+b[i];
    }
    cout << setprecision(4) << fixed << max(ld(0),ternery()) << endl; 
}

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