Submission #1261740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261740		mentarios	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	488 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ ios_base::sync_with_stdio(0); cin.tie(0);

int main() { _
    int S, N;
    cin >> S >> N;

    vector<ll> dp(S + 1, 0);

    for (int i = 0; i < N; i++) {
        ll v, w, k; // Valor, Peso, Quantidade
        cin >> v >> w >> k;

        // Se o item é efetivamente ilimitado, usamos a DP O(S) padrão.
        if (k * w >= S) {
            for (int j = w; j <= S; j++) {
                dp[j] = max(dp[j], dp[j - w] + v);
            }
        } else {
            // Se o item é limitado, usamos a otimização O(S) com fila monotônica.
            for (int rem = 0; rem < w; rem++) {
                deque<pair<ll, ll>> dq;
                for (int j = rem; j <= S; j += w) {
                    
                    // --- CORREÇÃO ESTÁ AQUI ---
                    // O valor que será usado para a fila deve ser baseado no estado
                    // de dp[j] ANTES de qualquer modificação nesta iteração.
                    ll val_para_fila = dp[j] - (j / w) * v;

                    // Remove da frente da fila os estados que estão fora da "janela" de k itens.
                    if (!dq.empty() && dq.front().second < j - k * w) {
                        dq.pop_front();
                    }
                    
                    // Calcula o NOVO valor de dp[j] usando o melhor da janela (que contém valores antigos).
                    if (!dq.empty()) {
                        dp[j] = max(dp[j], dq.front().first + (j / w) * v);
                    }

                    // Mantém a fila monotônica, removendo piores elementos do final.
                    while (!dq.empty() && dq.back().first <= val_para_fila) {
                        dq.pop_back();
                    }
                    // Insere o valor (baseado no estado antigo) na fila para futuras iterações.
                    dq.push_back({val_para_fila, j});
                }
            }
        }
    }

    cout << dp[S] << endl;
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27