Submission #944938

#TimeUsernameProblemLanguageResultExecution timeMemory
944938vako_pKnapsack (NOI18_knapsack)C++14
100 / 100
67 ms8816 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ll long long const int mxN = 2e5 + 5; ll n,s,v1,w1,k1,dp[mxN]; multiset<pair<ll,ll>> st[2005]; vector<ll> v,w,k; pair<ll,ll> x; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> s >> n; for(int i = 0; i < n; i++){ cin >> v1 >> w1 >> k1; st[w1].insert({v1, k1}); } ll curr; for(int i = 1; i <= s; i++){ curr = 0; auto it = st[i].end(); while(it != st[i].begin() and curr < s / i){ --it; x = *it; v.pb(x.first); w.pb(i); if(curr + x.second <= s / i){ k.pb(x.second); curr += x.second; } else{ k.pb(s / i - curr); curr = s / i; } } } n = v.size(); for(int i = 0; i < n; i++){ for(int j = s; j > 0; j--){ for(int l = 1; l <= k[i]; l++){ if(l * w[i] > j) break; dp[j] = max(dp[j], dp[j - l * w[i]] + v[i] * l); } } } cout << dp[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...