Submission #918324

#TimeUsernameProblemLanguageResultExecution timeMemory
918324kotnidKnapsack (NOI18_knapsack)C++14
100 / 100
38 ms4956 KiB
/* knapsack with multiple amount -> express as 2^0, 2^1,.... */ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pii; int main(){ ios::sync_with_stdio(0); cin.tie(0); ll s, n; cin >> s >> n; ll dp[s+1]; memset(dp,0,sizeof dp); vector<pii> weight[s+1]; for(int i=0; i<n; i++){ ll v, w, k; cin >> v >> w >> k; weight[w].push_back({v,k}); } for(int i=1; i<=s; i++){ sort(weight[i].begin(), weight[i].end(), greater<pii>()); ll cnt = 0; for(auto [v,k]:weight[i]){ cnt += i*k; ll c = 1; while(c <= k){ ll v2 = v*c, w2 = i*c; for(int j=s; j>=w2; j--)dp[j] = max(dp[j], dp[j-w2]+v2); k -= c; c *= 2; } if(k != 0){ ll v2 = v*k, w2 = i*k; for(int j=s; j>=w2; j--)dp[j] = max(dp[j], dp[j-w2]+v2); } if(cnt > s)break; } } cout << dp[s]; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:38:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for(auto [v,k]:weight[i]){
      |                  ^
#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...