제출 #1219526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219526		pauloaph	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	328 KiB

knapsack

#include<iostream>
#include<algorithm>
#include <cmath>
#include<deque>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MANXN =  100000;

int fila[MANXN];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int C;
    int n;

    cin >> C >> n;

    long long v, w, b;
    long int dp[2][C+1];
    int prev = 0, act = 1;

    for ( int c = 0; c <= C; ++c )
      dp[prev][c] = 0;


    for (int i = 0; i < n; i++) {
        cin >> v >> w >> b;

        // Iteramos para cada capacidade, assumindo que o resto vai de 0 a w -1
        for(int resto=0; resto < w; resto++){ 

            int head=0, tail=-1;

            // c%w = Para capacidade c se pegarmos o item de peso w, j vezes, quanto sobra de capacidade
            // Como temos até b vezes o item, interamos usando j, 
            for(int c = resto; c <= C ; c +=w){    

                //Andamos na fila, atualizando o index da cabeça da fila
                //Até o valor da fila for menor que o novo valor - o delta
                if(head <= tail && fila[head] < c-b*w) {
                    head++;
                }
                while(head <= tail && dp[prev][fila[tail]] - fila[tail]/w*v < dp[prev][c] - c/w*v) {
                    tail--;
                }


                fila[++tail] = c;

                //para capacidade c qual o max valor possivel
                // c - fila[head] -> capacidade atual - o max da fila /w - > quantos items de peso w * valor v unitario
                dp[act][c] = dp[prev][fila[head]] + (c-fila[head])/w*v;  
            }
        }
        swap( act, prev );

    }
   cout << dp[prev][C] << endl;
   return 0;
}

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