Submission #1218631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218631		pauloaph	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	1352 KiB

knapsack

#include<iostream>
#include<algorithm>
#include <cmath>
using namespace std;

const int MAXN =  100000;
const int MAXC = 1000;

int main(){

    int C;
    int n;

    cin >> C >> n;

    int V[n];
    int W[n];
    int B[n];
    

    for (int i = 0; i < n; i++){
        cin >> V[i] >> W[i] >> B[i];
    }

//     long int NW[MAXN];
//     long int NV[MAXN];
//     long int M = 0;


//     // vamos criar os novos itens (pacotes)
//     for ( int i = 0; i < n; ++i ){
//         int pos = 0;
//         // procuramos o bit mais significativo
//         while ( (1 << pos) < B[i] )
//             pos++;
//         // aqui sabemos que (2 ^ pos) >= B[i]
//         pos--;
//         // agora 2 ^ pos < B[i], logo (2 ^ pos) - 1 <= B[i] 
//         while ( pos >= 0 ){
//             NW[M] = (1 << pos) * W[i];
//             NV[M] = (1 << pos) * V[i];
//             B[i] -= (1 << pos);
//             M++;
//             pos--;
//         }
//         if ( B[i] ){ // se sobrou um resto
//             NW[M] = B[i] * W[i];
//             NV[M] = B[i] * V[i];
//             M++;
//             B[i] = 0;
//         }
//     }

//    long long int dp[M + 1][C + 1];

//    // caso base : quando nao temos mais itens
//    for ( int c = 0; c <= C; ++c )
//       dp[M][c] = 0;

//    for ( int i = M - 1; i >= 0; --i )
//       for ( int c = 0; c <= C; ++c ){
//          dp[i][c] = dp[i + 1][c];
//          if ( NW[i] <= c )
//             dp[i][c] = max( dp[i][c], dp[i + 1][c - NW[i]] + NV[i] );
//       }

      // caso base : quando nao temos mais itens

    int dp[2][C+1];
    int prev = 0, act = 1;
    // caso base : quando nao temos mais itens
    for ( int c = 0; c <= C; ++c )
        dp[prev][c] = 0;


    for ( int i = n - 1; i >= 0; --i ){
        for ( int c = 0; c <= C; ++c ){
            dp[act][c] = 0;  // nao escolhemos nada
            for ( int k = 0; W[i]*k <= c && k <= B[i]; ++k ) // testamos cada possibilidade
                dp[act][c] = max( dp[act][c], dp[prev][c - k*W[i]] + k*V[i] );
        }
        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