Submission #1261754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261754		mentarios	Knapsack (NOI18_knapsack)	C++17	100 / 100	855 ms	464 KiB

knapsack

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>

using namespace std;
typedef long long ll;

// dp[j] = valor máximo para a capacidade j
// Usar array C-style global pode ser um pouco mais rápido
ll dp[2001]; 
// deque manual para performance
pair<ll, int> dq[2001]; 

int main() {
    // Usar scanf/printf para I/O mais rápido
    int S, N;
    scanf("%d %d", &S, &N);

    for (int i = 0; i < N; i++) {
        int v, w, k; // Valor, Peso, Quantidade
        scanf("%d %d %d", &v, &w, &k);

        if (w == 0) continue;

        // Se o item é efetivamente ilimitado, usamos a DP O(S) padrão
        if ((ll)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 com fila monotônica
            for (int rem = 0; rem < w; rem++) {
                int head = 0, tail = -1; // "Deque" manual

                for (int q = 0, j = rem; j <= S; j += w, q++) {
                    // Remove da frente os que estão fora da janela de `k` itens
                    if (head <= tail && dq[head].second < q - k) {
                        head++;
                    }

                    // Prepara o valor para a fila ser usado no FUTURO
                    // Este valor é baseado no estado de dp[j] de ANTES da atualização
                    ll val_para_fila = dp[j] - (ll)q * v;

                    // Mantém a fila monotônica (valores decrescentes)
                    while (head <= tail && dq[tail].first <= val_para_fila) {
                        tail--;
                    }
                    
                    // Adiciona o valor atual no fim da fila
                    tail++;
                    dq[tail] = {val_para_fila, q};

                    // ATUALIZA o dp[j] (estado novo) usando o melhor da fila (que veio do estado antigo)
                    if (head <= tail) {
                        dp[j] = max(dp[j], dq[head].first + (ll)q * v);
                    }
                }
            }
        }
    }

    printf("%lld\n", dp[S]);
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d %d", &S, &N);
      |     ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d %d %d", &v, &w, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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