제출 #745409

#제출 시각아이디문제언어결과실행 시간메모리
745409pemguimnKnapsack (NOI18_knapsack)C++14
73 / 100
264 ms262144 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define pb push_back #define gcd __gcd #define endl "\n" #define task "hihi" using namespace std; const int N = 2e6 + 5, MOD = 1e9 + 7; int n, s, dp[N]; vector<pii> items; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen(task".inp", "r", stdin); //freopen(task".out", "w", stdout); cin >> s >> n; for(int i = 1; i <= n; i++){ int v, w, k; cin >> v >> w >> k; k = min(k, s / w); for(int j = 1; j <= k; j++) items.pb({v, w}); } for(pii x : items){ for(int i = s; i >= x.second; i--){ dp[i] = max(dp[i], dp[i - x.second] + x.first); } } int ans = 0; for(int i = s; i >= 0; i--) ans = max(ans, dp[i]); cout << ans; 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...