Submission #343267

#	Time	Username	Problem	Language	Result	Execution time	Memory
343267		qwerasdfzxcl	Sure Bet (CEOI17_sure)	C++14	60 / 100	86 ms	2796 KiB

sure

/*#include <bits/stdc++.h>

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

ll query(ll val, int ac, int idx){
    ll ret=val-(ll)(idx+ac)*10000, tmp=bsum[idx]-(ll)(idx+ac)*10000;
    //printf("%lld %d %d: %lld\n", val, ac, idx, min(ret, tmp));
    return min(ret, tmp);
}

int psearch(ll val, int ac){
    int l=1, r=n-1, 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;
    }
    sort(a, a+n, greater<int>());
    sort(b, b+n, greater<int>());
    for (int i=0;i<n;i++){
        bsum[i+1]=bsum[i]+b[i];
    }
    ll ans=0, tmp=0;
    if (n<=1010){
        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;
}
*/

#include <bits/stdc++.h>

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

double query(double val, int ac, int idx){
    double ret=val-(idx+ac), tmp=bsum[idx]-(idx+ac);
    //printf("%lf %d %d: %lf\n", val, ac, idx, min(ret, tmp));
    return min(ret, tmp);
}

int psearch(double val, int ac){
    int l=1, r=n, ret=1;
    while(l<=r){
        int m=(l+r)/2;
        double tmp=query(val, ac, m)-query(val, ac, m+1);
        if (tmp>=(double)0.999999 && tmp<=(double)1.000001){
            ret=m;
            r=m-1;
        }
        else l=m+1;
    }
    return ret;
}

int main(){
    scanf("%d", &n);
    for (int i=0;i<n;i++){
        scanf("%lf %lf", &a[i], &b[i]);
    }
    sort(a, a+n, greater<double>());
    sort(b, b+n, greater<double>());
    for (int i=0;i<n;i++){
        bsum[i+1]=bsum[i]+b[i];
    }
    double ans=0, tmp=0;
    if (n<=1010){
        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);
            }
        }
        printf("%.4lf", ans);
        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);
    }
    printf("%.4lf", ans);
    return 0;
}

Compilation message (stderr)

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

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