← Real problems

ceoi17p2

mediumgreedyprefix-sumsbinary-searchStatement on DMOJ

CP Lang

13 lines0.3 spec
// ceoi17p2 Sure Bet: bet on the i best A odds and the j best B odds; the profit is
// min(A_i, B_j) - i - j for the two prefix sums. For each i the best j sits where the B prefix
// sum crosses the A prefix sum, so check the cut there and the one before it.
let n = read<1..=100_000>()
let odds = read<[n](a: F64, b: F64)>()
let sa = odds.map(o => o.a).sorted(by: desc).scan(+)
let sb = odds.map(o => o.b).sorted(by: desc).scan(+)
var best = 0.0
for i in sa.keys:
    let j = sb.keys.first_true(c => sb[c] >= sa[i]) ?? sb.keys.last!
    for k in [j, j.prev ?? j]:
        best max= min(sa[i], sb[k]) - F64(Int(i) + Int(k))
print(best, precision: 4)

Accepted C++

80 lines · 3.43 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int maxn = 1e5 + 5;

double arr[2][maxn];

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[0][i] >> arr[1][i];
    }
    for (auto& a : arr) {
        sort(a, a + n, greater<>());
    }
    auto check = [&](double x) -> bool {
        int ptr[2] {};
        double sm[2] {};
        while (sm[0] < x || sm[1] < x) {
            for (int i = 0; i < 2; i++) {
                if (sm[i] < x) {
                    if (ptr[i] == n) {
                        return false;
                    }
                    sm[i] += arr[i][ptr[i]++];
                    sm[0]--;
                    sm[1]--;
                }
            }
        }
        return true;
    };
    double l = 0, r = 1e18;
    for (int i = 0; i < 200; i++) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << l << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(4);
    solve();
}