제출 #841906

#제출 시각아이디문제언어결과실행 시간메모리
841906vjudge1Sure Bet (CEOI17_sure)C++17
100 / 100
71 ms13252 KiB
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define FOR(i,a,b) for(int i = (a) ; i <= (b) ; i++)
#define FORE(i,a,b) for(int i = (a) ; i >= (b) ; i--)
#define par pair<int , int>
#define bit(x,i) ((x>>i)&1)

using namespace std;

const int N = 1 << 20;
const int INF = INT_MAX;
const int mod = 1e9+7;

int MAX(int x, int y){
    if(x >= y) return x;
    else return y;
}

int MIN(int x, int y){
    if(x <= y) return x;
    else return y;
}

int n;
double a[N],b[N],ans1,ans2,ans;
double more;
double F[N],G[N];
int m1,m2,l,r;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    sort(a+1,a+n+1,[](double u, double v){
        return u > v;
    });
    sort(b+1,b+n+1,[](double u, double v){
        return u > v;
    });
    for(int i = 1 ; i <= n ; i++){
        F[i] = F[i-1] + a[i];
        G[i] = G[i-1] + b[i];
    }
    for(int i = 0 ; i <= n ; i++){
        l = 0;
        r = n;
        while(r-l > 2){
            m1 = l+(r-l)/3;
            if(G[m1]-i <= F[i]-m1){
                l = m1;
            }
            else{
                r = m1;
            }
        }
        for(int j = 0 ; j <= 3 ; j++){
            if(l+j <= n){
                ans = max(ans,min(G[l+j]-i,F[i]-l-j));
            }
            if(l-j >= 0){
                ans = max(ans,min(G[l-j]-i,F[i]-l+j));
            }
        }
    }
    cout << setprecision(4) << fixed << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...