제출 #571190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571190		piOOE	Sure Bet (CEOI17_sure)	C++17	100 / 100	98 ms	6732 KiB

sure

#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int N = 100001, infI = 1e9 + 7;
const ll infL = 3e18;

double a[N], b[N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    sort(a, a + n, greater<>());
    sort(b, b + n, greater<>());
    double ans = 0, suma = 0, sumb = 0;
    vector<tuple<double, int, int>> v(2 * n);
    for (int i = 0; i < n; ++i) {
        suma += a[i];
        sumb += b[i];
        v[i] = {suma, i + 1, 0};
        v[i + n] = {sumb, i + 1, 1};
    }
    sort(all(v));
    int mn[2] = {infI, infI};
    for (int i = 2 * n - 1; i > -1; --i) {
        ckmx(ans, get<0>(v[i]) - get<1>(v[i]) - mn[get<2>(v[i]) ^ 1]);
        ckmn(mn[get<2>(v[i])], get<1>(v[i]));
    }
    cout << fixed << setprecision(4) << ans;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40