Submission #928281

#	Time	Username	Problem	Language	Result	Execution time	Memory
928281		CSQ31	Knapsack (NOI18_knapsack)	C++17	37 / 100	1028 ms	66460 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[2222];
int main()
{
   int s,n;
   cin>>s>>n;

   vector<pair<ll,ll>>items;
   for(int i=0;i<n;i++){
    ll v,w,k;
    cin>>v>>w>>k;
    for(int j=0;j<k;j++)items.push_back({v,w});
   }

   for(auto x : items){
    int v = x.first;
    int w = x.second;
    for(int i = s;i >= w;i--)dp[i] = max(dp[i],dp[i - w] + v);
   }
   ll ans = 0;
   for(int i=0;i<=s;i++)ans = max(ans,dp[i]);
   cout<<ans<<'\n';
}

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