제출 #628056

#제출 시각아이디문제언어결과실행 시간메모리
628056ducanhle_Knapsack (NOI18_knapsack)C++14
73 / 100
483 ms596 KiB
#include <bits/stdc++.h> #define endl "\n" using namespace std; const int MAXN = 2e3 + 5; int n, dp[MAXN], s; struct item{ int v, w, k; } items[105]; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> s >> n; for (int i = 1; i <= n; i++){ cin >> items[i].v >> items[i].w >> items[i].k; } for (int i = 1; i <= n; i++){ for (int w = s; w >= 0; w--){ for (int k = 1; k <= min(items[i].k, s / items[i].w); k++){ if (w - k * items[i].w >= 0) dp[w] = max(dp[w], dp[w - k * items[i].w] + k * items[i].v); } } } cout << *max_element(dp, dp + s + 1) << endl; }
#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...