Submission #1274297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274297		MisterReaper	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	9 ms	464 KiB

Main

// File election.cpp created on 29.09.2025 at 20:44:48
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int inf = int(1E6);

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cout << std::fixed << std::setprecision(9);

    int N, K;
    std::cin >> N >> K;

    std::vector<std::array<int, 2>> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i][0] >> A[i][1];
        if (A[i][1] == -1) {
            A[i][1] = inf;
        }
    }

    std::sort(A.begin(), A.end(), [&](auto lhs, auto rhs) {
        return std::pair{lhs[1], lhs[0]} < std::pair{rhs[1], rhs[0]};
    });

    auto solve = [&](int x) -> double {
        std::vector<double> f(N + 1, inf), g(N + 1, inf);
        f[0] = 0;
        for (int k = 0; k < N; ++k) {
            std::vector<double> nf(N + 1, inf), ng(N + 1, inf);
            for (int j = 0; j <= std::min(k, K); ++j) {
                int i = k - j;
                if (i == x - 1) {
                    chmin(ng[i + j + 1], f[j] + 1.d * A[k][1] / (i + 1));
                } else {
                    chmin(nf[j], f[j] + 1.d * A[k][1] / (i + 1));
                }
                chmin(nf[j + 1], f[j] + 1.d * A[k][0] / (x + 1));
            }
            for (int i = 0; i <= std::min(k, K); ++i) {
                chmin(ng[i], g[i]);
                chmin(ng[i + 1], g[i] + 1.d * A[k][0] / (x + 1));
            }
            f = std::move(nf);
            g = std::move(ng);
        }
        return g[K];
    };

    double ans = 0;
    {
        auto B = A;
        std::sort(B.begin(), B.end());
        for (int i = 0; i < K; ++i) {
            ans += B[i][0];
        }
        debug(ans);
    }

    // for (int i = 1; i <= K; ++i) {
    //     double res = solve(i);
    //     debug(res);
    //     ans = std::min(ans, res);
    // }

    int lo = 1, hi = K;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        double smid = solve(mid);
        double smidp = solve(mid + 1);
        ans = std::min({ans, smid, smidp});
        if (smid > smidp) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    std::cout << ans << '\n';

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23