Submission #759824

#TimeUsernameProblemLanguageResultExecution timeMemory
759824sofija6Knapsack (NOI18_knapsack)C++14
73 / 100
1075 ms5044 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 100010 #define MAXS 2010 using namespace std; set<pair<ll,ll> > val[MAXS]; vector<ll> cnt[MAXN]; ll dp[MAXS],v[MAXN],w[MAXN],k[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll s,n,ans=0; cin >> s >> n; for (ll i=1;i<=n;i++) { cin >> v[i] >> w[i] >> k[i]; for (ll j=1;j<=k[i] && j*w[i]<=s;j++) { val[j*w[i]].insert({j*v[i],i}); if (val[j*w[i]].size()*j*w[i]>s) val[j*w[i]].erase(*(val[j*w[i]].begin())); } } for (ll i=1;i<=s;i++) { for (auto j : val[i]) cnt[j.second].push_back(i/w[j.second]); } for (ll i=1;i<=n;i++) { for (ll j=s;j>=0;j--) { for (ll l : cnt[i]) { if (j+l*w[i]>s) break; dp[j+l*w[i]]=max(dp[j+l*w[i]],dp[j]+l*v[i]); } } } for (ll i=0;i<=s;i++) ans=max(ans,dp[i]); cout << ans; return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:20:42: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   20 |             if (val[j*w[i]].size()*j*w[i]>s)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...