Submission #1241643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241643		ak5028	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	328 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
typedef long long  int ll;

int main(){
   ll s,n;cin>>s>>n;
   vector<ll>a,val,times;
   for(ll i=1;i<=n;i++){
      ll v,w,k;
      cin>>v>>w>>k;
      val.push_back(v);
      a.push_back(w);
      times.push_back(k);
   }
   vector<ll>dp(s+1);
   dp[0]=0;
   for(ll i=0;i<n;i++){
      for(ll f=1;f<=times[i];f++){
         ll r=a[i]*f;
         ll h=val[i]*f;
         if(r>s){break;}
         dp[r]=max(dp[r],h);
      }
      for(ll j=s;j>=a[i];j--){
         dp[j]=max(dp[j],dp[j-a[i]]+val[i]);
      }
   }
   cout<<dp[s];
}

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