oj.uz

Submission #343216

# Submission time Handle Problem Language Result Execution time Memory
343216 2021-01-03T14:29:27 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;
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<=2000){
        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\n", 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\n", rans);
    return 0;
}

Compilation message

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.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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct