Submission #1100064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100064		iwtbab	Knapsack (NOI18_knapsack)	C++14	100 / 100	115 ms	5116 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long

using namespace std;
using pll = pair<ll,ll>;
const int N=1e5+5, mod=998244353;

struct Item{
   ll w,v,k;
};

bool cmp(Item i1,Item i2){
   if(i1.w == i2.w) return i1.v > i2.v;
   return i1.w < i2.w;
}

//dp[j] = max(dp[j], dp[j - z*w[i]] + z*v[i])

int main(){
   int tar, n; cin >> tar >> n;
   vector<Item> items;

   for(int i=0;i<n;i++){
      ll w,v,k; cin>>v >> w >> k;
      items.push_back({w,v,k});
   }
   sort(items.begin(),items.end(),cmp);
   map<ll,ll> mp; // total objects can take with this weight

   // w: {item_v1,item_v2,item_v3} which v1 > v2 > v3 .... -> proritize
   vector<Item> newItems;
   for(Item&item:items){
      if(mp[item.w] * item.w > tar) continue;
      mp[item.w] += item.k;
      newItems.push_back(item);
   }
   swap(newItems, items);
   ll dp[tar + 1];

   memset(dp,0,sizeof(dp));
   ll ans = 0;
   for(int i=0;i<items.size();i++){
      for(int j=tar;j>=0;j--){
         int cnt=0;
         while(cnt * items[i].w <= j && cnt<=items[i].k){
            dp[j] = max(dp[j],dp[j-cnt*items[i].w] + items[i].v*cnt);
            cnt++;
         }
         ans = max(dp[j],ans);
      }
   }
   cout << ans << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int i=0;i<items.size();i++){
      |                ~^~~~~~~~~~~~~

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