Submission #1221431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221431		mifzal5331	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	1588 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main(){
  int kapasitas, barang; cin >> kapasitas >> barang;
  vector<int> harga(barang), berat(barang), stok(barang);
  vector<ll> dp(kapasitas + 1, 0);
  for(int i = 0; i < barang; i++){
    cin >> harga[i] >> berat[i] >> stok[i];
  }
  for(int i = 0; i < barang; i++){
    int semua = stok[i];
    for(int j = 1; semua > 0; j <<= 1){
      int quantitas = min(semua, j);
      semua -= quantitas;
      ll beratsemua = 1LL * quantitas * berat[i];
      ll hargatotal = 1LL * quantitas * harga[i];
      for(int k = kapasitas; k >= beratsemua; k--){
        dp[k] = max(dp[k], dp[k - beratsemua] + hargatotal);
      }
    }
  }
  cout << dp[kapasitas] << '\n';
}

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