Submission #593763

#	Time	Username	Problem	Language	Result	Execution time	Memory
593763		piOOE	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	47 ms	2300 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using db = double;

const int N = 501;

db dp[N][N]; //id, # of b's

db solved[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K;
    cin >> n >> K;
    vector<int> a(n), b(n), ob(n), oa(n);
    int cntb = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        if (b[i] != -1) {
            cntb += 1;
        }
    }
    iota(oa.begin(), oa.end(), 0), iota(ob.begin(), ob.end(), 0);
    sort(oa.begin(), oa.end(), [&a](int i, int j) {
        return a[i] < a[j];
    });
    sort(ob.begin(), ob.end(), [&](int i, int j) {
        if (b[i] == -1) return false;
        if (b[j] == -1) return true;
        return b[i] < b[j];
    });
    const db inf = 1e12;
    auto solve = [&](int mx) -> db {
        if (solved[mx] == 0) {
            for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) dp[i][j] = inf;
            dp[0][0] = 0;
            db ans = inf;
            vector<bool> used(n);
            auto relax = [&](int cnt, db start) {
                int done = cnt;
                if (done > K) {
                    return;
                }
                db now = start;
                for (int j: oa) {
                    if (done < K && !used[j]) {
                        done += 1;
                        now += a[j] / db(mx + 1);
                    }
                }
                ans = min(ans, now);
            };
            for (int i = 1; i <= n; ++i) {
                int idx = ob[i - 1];
                relax(i - 1, dp[i - 1][mx]);
                if (b[idx] == -1) {
                    break;
                }
                for (int k = 0; k <= min(mx, i); ++k) {
                    int x = i - k;
                    if (x < 0 || dp[i - 1][k] == inf || x + k > K) {
                        continue;
                    }
                    dp[i][k] = min(dp[i][k], dp[i - 1][k] + a[idx] / db(mx + 1));
                    if (k != mx) {
                        dp[i][k + 1] = min(dp[i][k + 1], dp[i - 1][k] + b[idx] / db(k + 1));
                    } else {
                        relax(k + x - 1, dp[i - 1][k]);
                    }
                }
                used[idx] = true;
                relax(i, dp[i][mx]);
            }
            solved[mx] = ans;
        }
        return solved[mx];
    };
    int r = min(K, cntb);
    int x = r / 2;
    for (int k = 9; k > -1; --k) {
        db ansL = (x >= (1 << k) ? solve(x - (1 << k)) : inf);
        db ans = solve(x);
        db ansR = (x + (1 << k) <= r ? solve(x + (1 << k)) : inf);
        if (ansL <= ans && ansL <= ansR) {
            x -= (1 << k);
        } else if (ansR <= ans) {
            x += (1 << k);
        }
    }
    cout << fixed << setprecision(3) << solve(x);
    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