Submission #1205469

#TimeUsernameProblemLanguageResultExecution timeMemory
1205469friendiksSure Bet (CEOI17_sure)C++20
0 / 100
0 ms324 KiB
#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC diagnostic ignored "-Wpedantic"
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(52);
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename V>
using table = gp_hash_table<T, V>;

using i128 = __int128;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;

const ll INF = 2e18;
const int inf = 2e9;
const int maxn = 1e5;
const int MOD = 988244353;
const ld pi = acos(-1);
const int P = 5167;
const int L = 26;
const ld EPS = 1e-7;

template<typename T, typename V>
void fill(T &container, V value) {
    for (auto &c: container)
        c = value;
}

#define int ll

void solve() {
    int n;
    cin >> n;
    vector<ld> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    vector<ld> pref_a(n + 1), pref_b(n + 1);
    for (int i = 0; i < n; ++i) {
        pref_a[i + 1] = pref_a[i] + a[i];
        pref_b[i + 1] = pref_b[i] + b[i];
    }
    ld ans = 0;
    for (int x = 0; x <= n; ++x) {
        int y = lower_bound(pref_b.begin(), pref_b.end(), pref_a[x]) - pref_b.begin();
        ans = max(ans, pref_a[x] - (x + y));
    }
    swap(pref_a, pref_b);
    cout << ans;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(4);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    //stress();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...