oj.uz

답안 #467371

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467371 2021-08-22T20:29:20 Z idk321 Sure Bet (CEOI17_sure) C++17
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

set<array<double, 2>> 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() && ((*it1)[1] + (*it2)[1]) <= 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:37:44: warning: narrowing conversion of '(i + 1)' from 'int' to 'double' [-Wnarrowing]
   37 |             setSum[j].insert({sum[j][i], i + 1});
      |                                          ~~^~~
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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -