Submission #1272492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272492		witek_cpp	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	1748 ms	8388 KiB

Main

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

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

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<pair<ld,ld>> elms;
    elms.reserve(n);
    for (int i = 0; i < n; ++i) {
        ld A, B;
        cin >> A >> B;
        if (B < 0) B = INF;            // brak pomagiera -> bardzo duże B
        elms.push_back({B, A});        // sortujemy po B, a przechowujemy (B,A)
    }
    sort(elms.begin(), elms.end());    // kupujemy pomagierów w rosnącej kolejności B

    // przepisujemy do 1-based arrays po sortowaniu
    vector<ld> A(n+1), B(n+1);
    for (int i = 0; i < n; ++i) {
        B[i+1] = elms[i].first;
        A[i+1] = elms[i].second;
    }

    // dp_kth_small[i][d] = minimalny czas potrzebny, aby z przedziału [i..n]
    // zdobyć dokładnie d głosów, jeśli od razu mamy (ile+1) mówiących (prędkość = ile+1).
    // dp[i][d] = minimalny czas potrzebny rozważając prefix pierwszych i stanów
    // żeby kupić dokładnie d pomagierów (i przy tym już "zarezerwować" czas
    // na pozyskane głosy z prefixu jako A/(ile+1)).
    vector<vector<ld>> dp_kth_small(n+2, vector<ld>(n+1, INF));
    vector<vector<ld>> dp(n+1, vector<ld>(n+1, INF));

    ld answer = INF;
    for (int ile = 0; ile <= n; ++ile) {
        // przygotuj dp_kth_small dla prędkości (ile+1)
        for (int d = 0; d <= n; ++d) dp_kth_small[n+1][d] = INF;
        dp_kth_small[n+1][0] = 0;
        for (int i = n; i >= 1; --i) {
            for (int d = 0; d <= n; ++d) {
                // nie bierz stanu i do głosów z suffixu
                dp_kth_small[i][d] = dp_kth_small[i+1][d];
                // weź ten stan jako jeden z d głosów (koszt A[i]/(ile+1))
                if (d > 0) dp_kth_small[i][d] = min(dp_kth_small[i][d], dp_kth_small[i+1][d-1] + A[i] / (ile + 1));
            }
        }

        // jeżeli nie kupujemy żadnego pomagiera, wynik to po prostu
        // minimalny czas aby zdobyć k głosów przy prędkości 1 (czyli ile+1 = 1)
        if (ile == 0) answer = min(answer, dp_kth_small[1][k]);

        // przygotuj dp dla prefixów
        for (int i = 0; i <= n; ++i) for (int d = 0; d <= n; ++d) dp[i][d] = INF;
        dp[0][0] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int d = 0; d <= i; ++d) {
                // opcja: nie kupujemy tutaj pomagiera -> "odkładamy" ten stan do fazy po kupnie wszystkich pomagierów
                if (dp[i-1][d] < INF) dp[i][d] = min(dp[i][d], dp[i-1][d] + A[i] / (ile + 1));
                // opcja: kupujemy tutaj pomagiera (d>=1). Przed zakupem mieliśmy (d-1) pomagierów,
                // czyli aktualna liczba mówiących to (d-1)+1 = d, więc koszt B[i]/d
                if (d >= 1 && dp[i-1][d-1] < INF) dp[i][d] = min(dp[i][d], dp[i-1][d-1] + B[i] / (ld)d);
                // jeżeli już kupiliśmy dokładnie 'ile' pomagierów w prefixie długości i,
                // to możemy połączyć czas wydany na kupno z czasem potrzebnym, żeby z suffixu [i+1..n]
                // zdobyć brakujące głosy. Tutaj używamy dokładnie tego samego mechanizmu
                // co w Twoim oryginalnym działającym kodzie.
                if (d == ile) {
                    int need_from_suffix = max(0, k - i); // tak jak w Twoim działającym kodzie
                    if (need_from_suffix <= n) {
                        answer = min(answer, dp[i][d] + dp_kth_small[i+1][need_from_suffix]);
                    }
                }
            }
        }
    }

    cout.setf(std::ios::fixed); cout << setprecision(9) << (double)answer << "\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