Submission #1296780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296780		quynhlam2012	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	588 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main(){
  FASTIO
  ll S,N; cin>>S>>N;
  vector<ll> dp(S+1,0);
  for(int i=0;i<N;i++){
    ll V,W,K; cin>>V>>W>>K;
    ll cnt=1;
    while(K>0){
      ll take=min(cnt,K);
      ll ww=W*take, vv=V*take;
      for(int j=S;j>=ww;j--) dp[j]=max(dp[j],dp[j-ww]+vv);
      K-=take;
      cnt*=2;
    }
  }
  cout<<dp[S];
}

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