Submission #1100000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100000		iwtbab	Knapsack (NOI18_knapsack)	C++14	73 / 100	1070 ms	2800 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;

ll dp[N],c[N],w[N],v[N];

//dp[j] = max(dp[j], dp[j - z*w[i]] + z*v[i])
map<ll,vector<pll>> mp;

int main(){
   int tar, n; cin >> tar >> n;
   for(int i=0;i<n;i++){
      ll w,v,k; cin>>v >> w >> k;
      mp[w].push_back({v,k});
   }

   ll ans = 0;
   memset(dp,0,sizeof(dp));
   // w: {v1...vn}
   for(auto&it:mp){
      sort(begin(it.second),end(it.second),greater<>());
      ll w = it.first;

      for(auto& p:it.second){
         ll v = p.first, copies=p.second;
         for(int j=tar;j>=0;j--){
            if(j < w) continue;
            for(int z=0;z<=copies;z++){
               if(j >= z*w)
                  dp[j] = max(dp[j], dp[j - z*w]+v*z);
               else break;
            }
            ans = max(dp[j],ans);
         }
      }
   }
   cout << ans << '\n';

}

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