제출 #879290

#제출 시각아이디문제언어결과실행 시간메모리
879290vjudge1Sure Bet (CEOI17_sure)C++17
100 / 100
93 ms11968 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define sz size
#define mp make_pair
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(a) a.begin(),a.end()
const int N=1e6+1;
const ll inf=1e18+1;
int n,k=0,mx=0,o=0;
ld v[N*2],d[N*2];
ld bin(int x)
{
    int l=0,m,r=x;
    while(l+1<r)
    {
        m=(l+r)>>1;
        if(v[m]>=d[x-m])
        {
            r=m;
        }
        else
        {
            l=m;
        }
    }
    return (max(v[r-1],d[x-r])-x);
}
int main()

{
    ios
    cin>>n;
    ld a[n],b[n],ans=0;;
    for(int i=0;i<n;++i)
    {
        cin>>a[i]>>b[i];
    }
    sort(a,a+n);sort(b,b+n);
    v[0]=d[0]=0;
    for(int i=0;i<=n*2;++i)
    {
        v[i+1]=v[i];
        d[i+1]=d[i];
        if(i<n)
        {
            v[i+1]+=a[n-i-1];
            d[i+1]+=b[n-1-i];
        }
    }
    for(int i=0;i<=n*2;++i)
    {
        ans=max(ans,bin(i));
    }
    cout<<fixed<<setprecision(4)<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...