Submission #1325096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325096		zwezdinv	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	106 ms	452 KiB

Main

#include<bits/stdc++.h>

using ll = long long;

signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, k;
    std::cin >> n >> k;
    std::vector<std::pair<int, int>> data(n);
    for (auto& [x, y] : data) std::cin >> x >> y;
    std::sort(data.begin(), data.end(), [&](auto a, auto b) {
        if (a.second == -1) return false;
        if (b.second == -1) return true;
        return a.second < b.second;
    });
    double ans = 1e18;
    for (int i = 1; i <= k; ++i) {
        std::vector<double> dp(n + 1, 1e18);
        dp[0] = 0;
        for (int j = 0; j < n; ++j) {
            for (int k = j; k >= 0; --k) {
                dp[k + 1] = std::min(dp[k + 1], dp[k] + 1.0 * data[j].first / i);
                int c = j - k + 1;
                double val = dp[k];
                dp[k] = 1e18;
                if (c < i) {
                    if (data[j].second != -1) {
                        dp[k] = val + 1.0 * data[j].second / c;
                    }
                } else {
                    dp[k] = val;
                }
            }
        }
        ans = std::min(ans, dp[k - i + 1]);
    }
    std::cout << std::fixed << std::setprecision(15) << ans;
}

• 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