Book Shop

Solution by dudu — 100 pts

Code / Notes

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

// TODO (later):
//  - Salvar os valores (so pra deixar mais rapido)

// TODO (now):
//  - nao deixar o dinheiro ficar negativo
//  - nao deixar passar na N-1'esima pagina

int N, M;
vector<int> price, pages;
vector<vector<int>> memo;
int maxPages(int pos, int money) {
    if (pos == N) {
        return 0;
    }
    if (memo[pos][money] != -1) {
        return memo[pos][money];
    }
    int dont = maxPages(pos+1, money);
    int buy = 0;
    if (price[pos] <= money) {
        buy = pages[pos] + maxPages(pos+1, money-price[pos]);
    }
    return memo[pos][money] = max(dont, buy);
}

// o que significa: maxPages(3, 5)
//  retorna o máximo de páginas que você pode conseguir (daqui pra frente)
//  a partir da posição 3, se você tem 5 de dinheiro

int main() {
    cin >> N >> M;

    memo.resize(N, vector<int>(M+1, -1));

    price.resize(N);
    pages.resize(N);
    for (auto &x : price) cin >> x;
    for (auto &x : pages) cin >> x;


    cout << maxPages(0, M) << endl;
}

Last updated 1 month ago

« Back to problem