제출 #1264486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264486		biank	Sure Bet (CEOI17_sure)	C++20	100 / 100	86 ms	6656 KiB

sure

#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define foreach(it, c) for (auto it = begin(c); it != end(c); it++)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back

using vi = vector<int>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using ii = pair<int, int>;

#define fst first
#define snd second

const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vector<ld> a(n), b(n);
    forn(i, n) cin >> a[i] >> b[i];
    sort(all(a), greater<ld>());
    sort(all(b), greater<ld>());
    vector<ld> prefA(n + 1), prefB(n + 1);
    forn(i, n) prefA[i + 1] = prefA[i] + a[i]; 
    forn(i, n) prefB[i + 1] = prefB[i] + b[i];
    ld ret = 0.0;
    forsn(s, 1, 2 * n + 1) {
        int lo = max(0, s - n) - 1, hi = min(n, s); 
        auto f = [&](int i) {
            assert(0 <= i && i <= n);
            assert(0 <= s - i && s - i <= n);
            return min(prefA[i], prefB[s - i]);
        };
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            if (f(mid) < f(mid + 1)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        ret = max(ret, f(hi) - s);
    }
    cout << fixed << setprecision(4) << ret << '\n';
    
    return 0;
}

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