Submission #587103

#	Time	Username	Problem	Language	Result	Execution time	Memory
587103		rgnerdplayer	Let's Win the Election (JOI22_ho_t3)	C++17	56 / 100	2593 ms	1156 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    auto solve = [&]() {
        int n, k;
        cin >> n >> k;

        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i] >> b[i];
            if (b[i] == -1) {
                b[i] = 1e9;
            }
        }

        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](auto i, auto j) {
            return pair(b[i], a[i]) < pair(b[j], a[j]);
        });

        // dp[i][votes][coord]
        double ans = 1e9;

        for (int x = 0; x <= k; x++) {
            vector dp(k + 1, vector<double>(x + 1, 1e9)), ndp(dp);
            dp[0][0] = 0;
            for (auto i : ord) {
                ndp = dp;
                for (int v = 0; v < k; v++) {
                    for (int c = 0; c <= x; c++) {
                        dp[v + 1][c] = min(dp[v + 1][c], ndp[v][c] + 1.0 * a[i] / (x + 1));
                        if (c < x) {
                            dp[v + 1][c + 1] = min(dp[v + 1][c + 1], ndp[v][c] + 1.0 * b[i] / (c + 1));
                        }
                    }
                }
            }
            ans = min(ans, dp[k][x]);
        }

        cout << fixed << setprecision(9) << ans << '\n';
    };
    
    solve();
    
    return 0;
}

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