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();
}