oj.uz

Submission #467465

# Submission time Handle Problem Language Result Execution time Memory
467465 2021-08-23T05:13:46 Z idk321 Sure Bet (CEOI17_sure) C++17
100 / 100
 145 ms 5160 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int N = 100005;
double odds [2][N];
 
double sum[2][N];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> odds[0][i] >> odds[1][i];
    }
    sort(odds[0], odds[0] + n, greater<double>());
    sort(odds[1], odds[1] + n, greater<double>());
 
    double res = 0;
    double val1 = 0;
    double val2 = 0;
    int a =  0;
    int b =  0;
 
    sum[0][0] = odds[0][0];
    sum[1][0] = odds[1][0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 2; j++) sum[j][i] = sum[j][i - 1] + odds[j][i];
    }
 
 
 
    for (int i = 0; i < n; i++) {
        double val1 = sum[0][i];
 
        int a = 0;
        int b = n - 1;
        while (a < b) {
            int mid = (a + b) / 2;
            double res1 = min(val1, sum[1][mid]) - i - mid - 2;
            double res2 = min(val1, sum[1][mid + 1]) - i - (mid + 1)- 2;
            res = max(res, res1);
            res = max(res, res2);
            if (res1 > res2) {
                b = mid;
            } else {
                a = mid + 1;
            }
        }
      res = max(res, min(val1, sum[1][a]) - i - a - 2);
    }
 
    cout << fixed << setprecision(4) << res << "\n";
}
 
/*
4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5
*/

Compilation message

sure.cpp: In function 'int main()':
sure.cpp:23:12: warning: unused variable 'val1' [-Wunused-variable]
   23 |     double val1 = 0;
      |            ^~~~
sure.cpp:24:12: warning: unused variable 'val2' [-Wunused-variable]
   24 |     double val2 = 0;
      |            ^~~~
sure.cpp:25:9: warning: unused variable 'a' [-Wunused-variable]
   25 |     int a =  0;
      |         ^
sure.cpp:26:9: warning: unused variable 'b' [-Wunused-variable]
   26 |     int b =  0;
      |         ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 125 ms 4676 KB Output is correct
18 Correct 107 ms 4732 KB Output is correct
19 Correct 105 ms 4712 KB Output is correct
20 Correct 104 ms 4784 KB Output is correct
21 Correct 122 ms 5064 KB Output is correct
22 Correct 121 ms 4712 KB Output is correct
23 Correct 103 ms 4884 KB Output is correct
24 Correct 102 ms 4728 KB Output is correct
25 Correct 106 ms 4772 KB Output is correct
26 Correct 145 ms 5160 KB Output is correct