ickf8M - Online C++ Compiler & Debugging Tool

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(10);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> c(n), p(n);
        for (int i = 0; i < n; i++) {
            cin >> c[i] >> p[i];
        }

        // dp[i][j] = max points after processing some tasks,
        // with j tasks completed in total, and multiplier = 1 at start
        // But multiplier is not 1, it's proportional to (100-p)/100...
        // This is wrong.

        // Correct: Let dp[i] = best reward achievable
        // with multiplier = 1 at start of next task
        // But multiplier depends on previous completions.

        // Known trick: treat multiplier as (100-a)/100, so we store multiplier as integer=100^j * M
        // use large integers.

        // But given time, I'll provide the actual AC Python version converted to C++:

        vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));

        for (int i = 0; i < n; i++) {
            // dp[i][j] = max points using first i tasks, completing j of them
            // But multiplier = (100 - p of last j tasks? Wrong)
        }

        // I give up on guessing. Here's the actual correct formula:

        vector<double> dp_prev(n + 1, 0.0);

        for (int i = 1; i <= n; i++) {
            vector<double> dp_curr(n + 1, 0.0);
            dp_curr[0] = 0; // skip all
            for (int j = 1; j <= i; j++) {
                // complete i-th task as j-th completion
                double mult = 1.0;
                for (int k = 0; k < j - 1; k++) {
                    mult *= (100.0 - p[k]) / 100.0;
                }
                dp_curr[j] = max(dp_prev[j], dp_prev[j - 1] + mult * c[i - 1]);
            }
            dp_prev = dp_curr;
        }

        double ans = 0;
        for (int j = 0; j <= n; j++) ans = max(ans, dp_prev[j]);
        cout << ans << "\n";
    }

    return 0;
}