This problem can be modeled as a dynamic programming problem where decisions are made annually to maximize profit. Each year, we have a certain amount of capital and can choose to invest in d different options. Each option j requires an initial investment of a[j] units and yields a profit of b[j] units per year. The goal is to maximize the total capital after n years.

The key insight is that the problem can be broken down into n independent annual stages. In each year, we aim to maximize the profit for that year based on the current capital. The total capitol after n years will be the sum of the initial capital and the accumulated profits from each year.

Initial Approach (Naive DP): A straightforward dynamic programming approach would involve a DP state dp[current_capital] representing the maximum profit achievable with current_capital. However, the maximum possible capital can grow exponentially, making this approach infeasible due to time and memory constraints.

The provided code snippet for the first task uses a DP approach where dp[k] represents the maximum profit obtainable by investing exactly k units of capital. The outer loop iterates through the number of years (n), and the inner loops iterate through investment options (d) and possible capital amounts. The state transition is dp[k] = max(dp[k], dp[k - a[j]] + b[j]). The total capital s is updated annually by adding the maximum profit achievable with the current capital s.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

const int MAX_OPTIONS = 15;
const int MAX_INITIAL_CAPITAL = 30000000;

int initialCapital, years, numOptions;
int investmentCost[MAX_OPTIONS];
int annualProfit[MAX_OPTIONS];
int maxProfit[MAX_INITIAL_CAPITAL];

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

    std::cin >> initialCapital >> years >> numOptions;
    for (int i = 1; i <= numOptions; ++i) {
        std::cin >> investmentCost[i] >> annualProfit[i];
    }

    for (int year = 0; year < years; ++year) {
        memset(maxProfit, 0, sizeof(maxProfit));
        for (int option = 1; option <= numOptions; ++option) {
            for (int currentCap = investmentCost[option]; currentCap <= initialCapital; ++currentCap) {
                maxProfit[currentCap] = std::max(maxProfit[currentCap], maxProfit[currentCap - investmentCost[option]] + annualProfit[option]);
            }
        }
        initialCapital += maxProfit[initialCapital];
    }

    std::cout << initialCapital << std::endl;
    return 0;
}

Optimizaton 1: Scaling Capital

A crucial observation is that the investment costs a[j] are multiples of 1000. This implies that only the capital amount divisible by 1000 affects the optimal investment strategy. The remainder (less than 1000) does not influence decisions regarding investments that are multiples of 1000. Therefore, we can scale down the capital and investment costs by dividing them by 1000. This significantly reduces the state space of our DP. The DP state dp[k] now represents the maximum profit for k * 1000 units of capital.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

const int MAX_OPTIONS = 15;
const int MAX_SCALED_CAPITAL = 46000; // Max initial capital 10^6 scaled down

int initialCapital, years, numOptions;
int investmentCost[MAX_OPTIONS];
int annualProfit[MAX_OPTIONS];
int maxProfit[MAX_SCALED_CAPITAL];

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

    std::cin >> initialCapital >> years >> numOptions;
    for (int i = 1; i <= numOptions; ++i) {
        std::cin >> investmentCost[i] >> annualProfit[i];
        investmentCost[i] /= 1000; // Scale down investment cost
    }
    initialCapital /= 1000; // Scale down initial capital

    for (int year = 0; year < years; ++year) {
        memset(maxProfit, 0, sizeof(maxProfit));
        for (int option = 1; option <= numOptions; ++option) {
            for (int currentScaledCap = investmentCost[option]; currentScaledCap <= initialCapital; ++currentScaledCap) {
                maxProfit[currentScaledCap] = std::max(maxProfit[currentScaledCap], maxProfit[currentScaledCap - investmentCost[option]] + annualProfit[option]);
            }
        }
        initialCapital += maxProfit[initialCapital];
    }

    std::cout << initialCapital * 1000 << std::endl; // Scale back up for output
    return 0;
}

Optimization 2: Incremental DP Updates

Notice that in the previous approach, the DP table is recomputed from scratch each year. However, the DP state dp[k] depends on previous states dp[k - a[j]]. Instead of resetting dp each year, we can update it incrementally. When considering investments for the current year, we can continue calculating from the state reached at the end of the previous year. This avoids redundant computations and further speeds up the process. The DP loop's starting point for k can be optimized. If the previous DP calculation ended at a certain capital m, the next year's calculation for a particular investment j only needs to consider capital amounts starting from m / 1000 (or a[j] if m is not yet determined for that year's option). The DP state dp[k] now represents the additional profit achievable for k * 1000 capital in the current year, building upon the profits from previous years.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

const int MAX_OPTIONS = 15;
const int MAX_SCALED_CAPITAL = 46000;

int initialCapital, years, numOptions;
int investmentCost[MAX_OPTIONS];
int annualProfit[MAX_OPTIONS];
int currentYearProfit[MAX_SCALED_CAPITAL];

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

    std::cin >> initialCapital >> years >> numOptions;
    for (int i = 1; i <= numOptions; ++i) {
        std::cin >> investmentCost[i] >> annualProfit[i];
        investmentCost[i] /= 1000; // Scale down investment cost
    }
    int scaledInitialCapital = initialCapital / 1000;

    int lastComputedCap = 0; // Tracks the upper bound of capital processed in the previous year's DP
    for (int year = 0; year < years; ++year) {
        memset(currentYearProfit, 0, sizeof(currentYearProfit));
        for (int option = 1; option <= numOptions; ++option) {
            // Start DP from either the investment cost or the last computed capital for this option
            int startCap = std::max(investmentCost[option], lastComputedCap / 1000);
            for (int currentScaledCap = startCap; currentScaledCap <= scaledInitialCapital; ++currentScaledCap) {
                currentYearProfit[currentScaledCap] = std::max(currentYearProfit[currentScaledCap], currentYearProfit[currentScaledCap - investmentCost[option]] + annualProfit[option]);
            }
        }
        // Add the maximum profit achievable for the current total capital to the total capital.
        // The profit `currentYearProfit[k]` is the *additional* profit for `k*1000` capital in this year.
        // We need the max profit for the *entire* available capital (`scaledInitialCapital`).
        // We find the maximum profit obtainable by investing *up to* scaledInitialCapital, by iterating through the DP table.
        int maxProfitThisYear = 0;
        for(int cap = 0; cap <= scaledInitialCapital; ++cap) {
            maxProfitThisYear = std::max(maxProfitThisYear, currentYearProfit[cap]);
        }
        scaledInitialCapital += maxProfitThisYear;
        lastComputedCap = scaledInitialCapital * 1000; // Update for the next year
    }

    std::cout << scaledInitialCapital * 1000 << std::endl; // Scale back up for output
    return 0;
}