lista 6

#include <iostream>

using namespace std;

// Função para calcular a diversão na t-ésima corrida do brinquedo
int calculaDiversaoBrinquedo(int S, int B, int t) {
    return S - (t - 1) * (t - 1) * B;
}

// Função para calcular a diversão máxima possível até o maior valor de créditos
void calculaDiversaoMaxima(int S[], int B[], int C[], int N, int K_max, int dp[]) {
    // Para cada brinquedo i
    for (int i = 0; i < N; i++) {
        // Para cada corrida no brinquedo i
        for (int corrida = 1;; corrida++) {
            int diversaoAtual = calculaDiversaoBrinquedo(S[i], B[i], corrida); // Diversão da t-ésima corrida
            int custoAtual = C[i]; // Custo de uma única corrida

            // Atualiza a tabela dp de trás para frente (para garantir que cada combinação de corridas seja usada uma vez)
            for (int j = K_max; j >= custoAtual; j--) {
                dp[j] = max(dp[j], dp[j - custoAtual] + diversaoAtual);
            }

             // Se a diversão for menor ou igual a 0 ou o custo ultrapassar os créditos disponíveis, parar
            if (diversaoAtual <= 0 || custoAtual*corrida >= K_max) {
                diversaoAtual = 0;
                break;
            }
        }
    }
}

int main() {
    int N; // Número de brinquedos
    cin >> N;

    int dp[25001] = {0};

    int S[1000], B[1000], C[1000]; // Arrays para armazenar diversão, aborrecimento e custo

    // Lendo as informações dos brinquedos
    for (int i = 0; i < N; i++) {
        cin >> S[i] >> B[i] >> C[i];
    }

    calculaDiversaoMaxima(S, B, C, N, 25001, dp);


    int V; // Número de visitas ao parque
    cin >> V;

    int visitas[100]; // Array para armazenar os créditos de cada visita
    int K_max = 0; // Variável para armazenar o maior valor de créditos entre as visitas

    // Lendo os créditos de cada visita e encontrando o maior valor de K
    for (int j = 0; j < V; j++) {
        cin >> visitas[j];

    }

    for (int j = 0; j < V; j++) {
        cout << j << ": " << dp[visitas[j]] << endl;
    }

    return 0;
}