Submission #633169

#TimeUsernameProblemLanguageResultExecution timeMemory
633169a_aguiloKnapsack (NOI18_knapsack)C++14
0 / 100
2 ms976 KiB
#include<bits/stdc++.h> using namespace std; typedef vector<long long int> vi; typedef vector<vi> vvi; vi dp; vi values, weight, freqs; int S, N; int main(){ cin >> S >> N; dp = vi(S+1, 0); values = vi(N); weight = vi(N); freqs = vi(N); for(int i = 0; i < N; ++i) cin >> values[i] >> weight[i] >> freqs[i]; vector<int> pos; pos.push_back(0); for(int i = 0; i < N; ++i){ for(int reps = 0; reps <= freqs[i]; ++reps){ for(int p: pos){ int nextW = p + weight[i]; if(nextW <= S) { dp[nextW] = max(dp[nextW], dp[p] + values[i]); pos.push_back(nextW); } } } } long long int ans = 0; for(long long int n: dp) ans = max(ans, n); 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...