Submission #405668

#	Time	Username	Problem	Language	Result	Execution time	Memory
405668		Hazem	Sure Bet (CEOI17_sure)	C++14	100 / 100	180 ms	4548 KiB

sure

#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 3e5+10;
const int M = 3e2+10;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;   
const double PI = 3.141592653589793;

vector<double>vec[2];
int n;
double pr[N];

double calc(double sum,double cnt){

    int l = 0,r = n-1;
    while(l<r){
        int mid = (l+r+1)/2;
        double ans1 = pr[mid]-cnt;
        if(ans1<=sum-mid-1)l = mid;
        else r = mid-1;
    }
    double ret = 0;
    for(int i=max(0,l-10);i<min(n,l+10);i++)
        ret = max(ret,min(pr[i]-cnt,sum-i-1));
    
    return ret;
}

int main(){

    //freopen("out.txt","w",stdout);

    scanf("%d",&n);

    for(int i=1;i<=n;i++)
        for(int j=0;j<2;j++){
            double x;cin>>x;
            vec[j].push_back(x);
        }

    for(int j=0;j<2;j++){
        sort(vec[j].begin(),vec[j].end());
        reverse(vec[j].begin(),vec[j].end());
    }

    for(int i=0;i<n;i++)
        pr[i] = (i?pr[i-1]:0)+vec[0][i]-1.0;

    double ans = 0,sum = 0;
    for(int i=0;i<n;i++){
        sum += vec[1][i]-1;
        ans = max(ans,calc(sum,i+1));
    }

    printf("%.4lf\n",ans);
}   

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~

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