Submission #1278164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278164		nanaseyuzuki	Let's Win the Election (JOI22_ho_t3)	C++20	0 / 100	221 ms	4396 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const double INF = 1e100;

struct Megumi { int a, b; };

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

    int n, K;
    if (!(cin >> n >> K)) return 0;
    vector<Megumi> e(n);
    for(int i=0;i<n;i++) cin >> e[i].a >> e[i].b;
    // Nếu muốn, sắp xếp theo b (đặt -1 thành very large) như trong đề
    sort(e.begin(), e.end(), [](const Megumi& x, const Megumi& y){
        int bx = (x.b == -1 ? INT_MAX : x.b);
        int by = (y.b == -1 ? INT_MAX : y.b);
        if (bx == by) return x.a < y.a;
        return bx < by;
    });

    // dp layer rolling: dp[j][k] = min time with j supporters (including you) and k cooperators
    vector<vector<double>> prev(K+1, vector<double>(K+1, INF));
    vector<vector<double>> cur(K+1, vector<double>(K+1, INF));

    prev[1][0] = 0.0; // start: bạn tự ủng hộ => j = 1, k = 0

    for(int i = 0; i < n; ++i){
        // reset cur
        for(int j = 1; j <= K; ++j)
            for(int k = 0; k <= K; ++k)
                cur[j][k] = INF;

        for(int j = 1; j <= K; ++j){
            for(int k = 0; k <= K; ++k){
                double base = prev[j][k];
                if (base >= INF) continue;

                // 1) do nothing
                cur[j][k] = min(cur[j][k], base);

                // 2) take a vote from this state -> now have j+1 supporters
                if (j + 1 <= K){
                    // cost uses current supporters count j
                    double cost = (double)e[i].a / (double)j;
                    cur[j+1][k] = min(cur[j+1][k], base + cost);
                }

                // 3) recruit a cooperator -> supporters stay j, cooperators increase
                if (e[i].b != -1 && k + 1 <= K){
                    double cost = (double)e[i].b / (double)j;
                    cur[j][k+1] = min(cur[j][k+1], base + cost);
                }
            }
        }
        swap(prev, cur);
    }

    double ans = INF;
    for(int k = 0; k <= K; ++k) ans = min(ans, prev[K][k]); // đạt K supporters (bao gồm bạn)
    if (ans >= INF/2) cout << "-1\n";
    else cout << fixed << setprecision(15) << ans << "\n";
    return 0;
}

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