Submission #343209

#	Time	Username	Problem	Language	Result	Execution time	Memory
343209		qwerasdfzxcl	Sure Bet (CEOI17_sure)	C++14	0 / 100	1 ms	364 KiB

sure

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int a[100100];
int b[100100];
int n;

ll query(ll val, int ac, int idx){
    ll ret=val-idx*10000, tmp=-ac*10000;
    for (int i=0;i<idx;i++){
        tmp += b[i];
    }
    return min(ret, tmp);
}

int psearch(ll val, int ac){
    int l=1, r=n-2, ret=1;
    while(l<=r){
        int m=(l+r)/2;
        if (query(val, ac, m)-query(val, ac, m+1)==10000){
            ret=m;
            r=m-1;
        }
        else l=m+1;
    }
    return ret;
}

int main(){
    scanf("%d", &n);
    for (int i=0;i<n;i++){
        double tmp1, tmp2;
        scanf("%lf %lf", &tmp1, &tmp2);
        a[i]=tmp1*10000;
        b[i]=tmp2*10000;
        a[i] -= 10000;
        b[i] -= 10000;
    }
    sort(a, a+n, greater<int>());
    sort(b, b+n, greater<int>());
    ll ans=0, tmp=0;
    if (n<=3){
        for (int i=0;i<n;i++){
            tmp += a[i];
            for (int j=0;j<=n;j++){
                ans=max(query(tmp, i+1, j), ans);
            }
        }
        double rans=ans;
        rans/=10000;
        printf("%.4lf", rans);
        return 0;
    }
    for (int i=0;i<n;i++){
        tmp += a[i];
        int idx=psearch(tmp, i+1);
        ans=max(max(query(tmp, i+1, idx-1), query(tmp, i+1, idx)), ans);
        //printf("%lld %d\n", ans, idx);
    }
    double rans=ans;
    rans/=10000;
    printf("%.4lf", rans);
    return 0;
}

Compilation message (stderr)

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

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