Submission #1266322

#TimeUsernameProblemLanguageResultExecution timeMemory
1266322nathlol2Knapsack (NOI18_knapsack)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int s, n; cin >> s >> n; vector<int> a, b; for(int i = 0;i<n;i++){ int p, w, m; cin >> p >> w >> m; for(int j = 1;j<=m;j++){ if(w * j > s){ break; } a.push_back(p * j); b.push_back(w * j); } } int sz = a.size(); vector<int> dp(s + 1), prev(s + 1); for(int i = 0;i<sz;i++){ for(int j = s;j>=b[i];j--){ dp[j] = max(dp[j], prev[j - b[i]] + a[i]); } swap(dp, prev); } cout << prev[s] << '\n'; }
#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...