Submission #173688

#TimeUsernameProblemLanguageResultExecution timeMemory
173688rzbtSure Bet (CEOI17_sure)C++14
100 / 100
88 ms5364 KiB
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;
int n;
double a[MAXN],b[MAXN],prefb[MAXN],prefa[MAXN],res;

int bin(int l,int d,int pa,int sol){
    if(l>d)return sol;
    int mid=(l+d)/2;
    if(prefa[pa]-mid>prefb[mid]-pa)return bin(mid+1,d,pa,mid);
    return bin(l,mid-1,pa,sol);
}


int main()///NE MORA DA VUDE POVEZAN
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%lf %lf",a+i,b+i);
    }
    double res=0.0;

    sort(a+1,a+1+n,greater<double>());
    sort(b+1,b+1+n,greater<double>());
    for(int i=1;i<=n;i++){
        prefb[i]=prefb[i-1]+b[i]-1.0;
        prefa[i]=prefa[i-1]+a[i]-1.0;
    }
    for(int i=1;i<=n;i++){
        int ok=bin(0,n,i,0);
        //printf("  %d %d    %f %f\n",i,ok,prefa[i],prefb[ok]);
        res=max(res,min(prefa[i]-ok,prefb[ok]-i));
        if(ok!=n)res=max(res,min(prefa[i]-ok-1,prefb[ok+1]-i));
    }
    printf("%.4f",res);

    return 0;
}

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
sure.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lf %lf",a+i,b+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...