Submission #1261729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261729		mentarios	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	328 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) {
                    // 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 valor da DP usando o melhor da janela
                    if (!dq.empty()) {
                        dp[j] = max(dp[j], dq.front().first + (j / w) * v);
                    }

                    // Prepara o valor atual para ser inserido na fila
                    ll val = dp[j] - (j / w) * v;

                    // Mantém a fila monotônica (decrescente), removendo piores elementos do final
                    while (!dq.empty() && dq.back().first <= val) {
                        dq.pop_back();
                    }
                    dq.push_back({val, j});
                }
            }
        }
    }

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

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