Submission #639503

#TimeUsernameProblemLanguageResultExecution timeMemory
639503a_aguiloKnapsack (NOI18_knapsack)C++14
100 / 100
215 ms37456 KiB
#include<bits/stdc++.h> using namespace std; typedef vector<long long int> vi; typedef vector<vi> vvi; vvi dp; vi values, weight, freqs; int S, N; int main(){ cin >> S >> N; dp = vvi(S+1, vi(S+1, 0)); values = vi(N); weight = vi(N); freqs = vi(N); vector<vector<pair<int, int>>> itemsWithWeight(S+1); for(int i = 0; i < N; ++i) { cin >> values[i] >> weight[i] >> freqs[i]; itemsWithWeight[weight[i]].push_back({values[i], freqs[i]}); } //cout << "a" << endl; for(int i = 0; i <=S; ++i)sort(itemsWithWeight[i].rbegin(), itemsWithWeight[i].rend()); //cout << "a" << endl; long long int ans = 0; for(int i = 1; i <= S; ++i){ for(int weight = 0; weight <= S; ++weight){ int accumulatedWeight = 0; int accumulatedValue = 0; dp[weight][i] = dp[weight][i-1]; ans = max(ans, dp[weight][i]); for(pair<int, int> item: itemsWithWeight[i]){ int myVal = item.first; int reps = item.second; for(int rep = 0; rep < reps; ++rep){ accumulatedWeight += i; accumulatedValue += myVal; if(accumulatedWeight > weight) break; dp[weight][i] = max(dp[weight][i], dp[weight - accumulatedWeight][i-1] + accumulatedValue); ans = max(ans, dp[weight][i]); } if(accumulatedWeight > weight) break; } } } cout << ans << endl; 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...