Submission #1221411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221411		mifzal5331	Knapsack (NOI18_knapsack)	C++20	37 / 100	1 ms	328 KiB

knapsack

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

int main(){
  long long kapasitas,barang; cin>>kapasitas>>barang;
  vector<int> harga(barang),berat(barang),stok(barang);
  vector<long long> 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;
      long long beratsemua=quantitas*berat[i],hargatotal=quantitas*harga[i];
      for(int k=kapasitas;k>=beratsemua;k--){
        dp[k]=max(dp[k],dp[k-beratsemua]+hargatotal);
      }
    }
  }
  cout<<dp[kapasitas];
}

//dp[j]=harga termahal dengan maksimal j kg kapasitas

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