Submission #759818

#TimeUsernameProblemLanguageResultExecution timeMemory
759818sofija6Knapsack (NOI18_knapsack)C++14
73 / 100
715 ms262144 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 100010 #define MAXS 2010 using namespace std; priority_queue<pair<ll,ll> > val[MAXS]; set<ll> cnt[MAXN]; ll dp[MAXS],v[MAXN],w[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll s,n,k,ans=0; cin >> s >> n; for (ll i=1;i<=n;i++) { cin >> v[i] >> w[i] >> k; for (ll j=1;j<=k && j*w[i]<=s;j++) val[j*w[i]].push({j*v[i],i}); } for (ll i=1;i<=s;i++) { ll cur=0; while (!val[i].empty()) { cur++; auto t=val[i].top(); val[i].pop(); if (cur*i<=s) cnt[t.second].insert(i/w[t.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]+v[i]*l); } } } for (ll i=0;i<=s;i++) ans=max(ans,dp[i]); cout << ans; return 0; }
#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...