oj.uz

Submission #545670

# Submission time Handle Problem Language Result Execution time Memory
545670 2022-04-05T06:55:19 Z Ai7081 Sure Bet (CEOI17_sure) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n;
double a[N], b[N], suma[N], sumb[N], out;

int main() {
    scanf(" %d", &n);
    for (int i=1; i<=n; i++) scanf(" %lf %lf", &a[i], &b[i]);
    sort(a+1, a+n+1, greater<double>()), sort(b+1, b+n+1, greater<double>());
    for (int i=1; i<=n; i++) suma[i] = suma[i-1] + a[i], sumb[i] = sumb[i-1] + b[i];
//    printf("suma : ");
//    for (int i=0; i<=n; i++) printf("%lf ", suma[i]);
//    printf("\nsumb : ");
//    for (int i=0; i<=n; i++) printf("%lf ", sumb[i]);
//    printf("\n");
    for (int k=2; k<=2*n-1; k++) {
        int l = max(1, k-n), r = min(n, k-1);
        //printf("%d %d %d : ", k, l, r);
        while (l < r) {
            int mid = (l+r)/2;
            if (suma[mid] < sumb[k-mid]) l = mid+1;
            else r = mid;
        }
        //printf("%d %.4lf %.4lf ans %.4lf\n", l, suma[l-1], sumb[k-l], max(suma[l-1], sumb[k-l]) - k);
        if (l == min(n, k-1) && suma[l] < sumb[k-l]) out = max(out, suma[l] - k);
        else if (l == max(1, k-n) && suma[l] >= sumb[k-l]) out = max(out, sumb[k-l] - k);
        else out = max(out, max(suma[l-1], sumb[k-l]) - k);
    }
    printf("%.4lf", out);
    return 0;
}

Compilation message

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -