Submission #434578

#	Time	Username	Problem	Language	Result	Execution time	Memory
434578		KoD	Sure Bet (CEOI17_sure)	C++17	0 / 100	1 ms	204 KiB

sure

#include <bits/stdc++.h>

template <class T> using Vec = std::vector<T>;

int parse() {
    std::string s;
    std::cin >> s;
    const auto t = s.find('.');
    if (t >= s.size()) {
        return 10000 * std::stoi(s);
    }
    while (t + 4 >= s.size()) {
        s.push_back('0');
    }
    return 10000 * std::stoi(s.substr(0, t)) + std::stoi(s.substr(t + 1));
}

int main() {
    int N;
    std::cin >> N;
    Vec<int> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        A[i] = parse();
        B[i] = parse();
    }
    std::sort(A.rbegin(), A.rend());
    std::sort(B.rbegin(), B.rend());
    long long ok = 0, ng = 1000000000000 + 5;
    while (ng - ok > 1) {
        const auto md = (ok + ng) / 2;
        int l = 0, r = 0;
        long long ls = 0, rs = 0;
        bool f = false;
        for (int k = 1; k <= 2 * N; ++k) {
            const auto need = md + k * 10000;
            while (l < N and ls < need) {
                ls += A[l];
                l += 1;
            }
            while (r < N and rs < need) {
                rs += B[r];
                r += 1;
            }
            if (ls >= need and rs >= need and l + r <= k) {
                f = true;
                break;
            }
        }
        (f ? ok : ng) = md;
    }
    std::cout << ok / 10000 << '.' << ok % 10000 << '\n';
    return 0;
}

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