oj.uz

Submission #467372

# Submission time Handle Problem Language Result Execution time Memory
467372 2021-08-22T20:40:19 Z idk321 Sure Bet (CEOI17_sure) C++17
100 / 100
 891 ms 19896 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
double odds [2][N];

set<tuple<double, int>> setSum[2];
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 j = 0; j < 2; j++) {
        for (int i = 0; i < n; i++) {
            setSum[j].insert({sum[j][i], i + 1});
        }
    }
    vector<double> allValues;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            allValues.push_back(sum[j][i]);
        }
    }
    sort(allValues.begin(), allValues.end());

    for (int i = 2; i <= 2 * n; i++) {
        int a = 0;
        int b = 2 * n - 1;
        double cres = -1;
        while (a <= b) {
            int mid = (a + b) / 2;
            auto it1 = setSum[0].lower_bound({allValues[mid], -1});
            auto it2 = setSum[1].lower_bound({allValues[mid], -1});
            //if (i == 3) cout << allValues[mid] << " " << a << " " << b << endl;
            if (it1 != setSum[0].end() && it2 != setSum[1].end() && (get<1>(*it1) + get<1>(*it2)) <= i) {
                cres = allValues[mid] - i;
                a = mid + 1;
            } else {
                b = mid - 1;
            }
        }

        res = max(res, cres);
    }

    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:25:12: warning: unused variable 'val1' [-Wunused-variable]
   25 |     double val1 = 0;
      |            ^~~~
sure.cpp:26:12: warning: unused variable 'val2' [-Wunused-variable]
   26 |     double val2 = 0;
      |            ^~~~
sure.cpp:27:9: warning: unused variable 'a' [-Wunused-variable]
   27 |     int a =  0;
      |         ^
sure.cpp:28:9: warning: unused variable 'b' [-Wunused-variable]
   28 |     int b =  0;
      |         ^

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 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 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Correct 3 ms 520 KB Output is correct
15 Correct 3 ms 460 KB Output is correct
16 Correct 3 ms 460 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 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 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Correct 3 ms 520 KB Output is correct
15 Correct 3 ms 460 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 775 ms 18064 KB Output is correct
18 Correct 775 ms 18068 KB Output is correct
19 Correct 746 ms 18264 KB Output is correct
20 Correct 774 ms 18124 KB Output is correct
21 Correct 819 ms 18104 KB Output is correct
22 Correct 808 ms 19484 KB Output is correct
23 Correct 825 ms 19416 KB Output is correct
24 Correct 767 ms 19512 KB Output is correct
25 Correct 849 ms 19468 KB Output is correct
26 Correct 891 ms 19896 KB Output is correct