oj.uz

Submission #343241

# Submission time Handle Problem Language Result Execution time Memory
343241 2021-01-03T14:58:01 Z qwerasdfzxcl Sure Bet (CEOI17_sure) C++14
0 / 100
 1 ms 364 KB 
#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-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;
    }
    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;
}

Compilation message

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Incorrect 0 ms 364 KB Output isn't correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Incorrect 0 ms 364 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Incorrect 0 ms 364 KB Output isn't correct