Submission #928285

#	Time	Username	Problem	Language	Result	Execution time	Memory
928285		CSQ31	Knapsack (NOI18_knapsack)	C++17	73 / 100	1075 ms	18344 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 i=0;;i++){
        ll p = (1LL<<i); 
        if(k>=p){
            k-=p;
            items.push_back({v*p,w*p});
        }
        else break;
    }
     if(k)items.push_back({v*k,w*k});
   }

   for(auto x : items){
    ll v = x.first;
    ll 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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27