Submission #1209816

#TimeUsernameProblemLanguageResultExecution timeMemory
1209816borekkingKnapsack (NOI18_knapsack)C++20
49 / 100
166 ms327680 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll s, n; cin >> s >> n; vector<ll> weight(1), profit(1); for (int i = 0; i < n; i++) { ll v, w, k; cin >> v >> w >> k; ll amount = min(s/w + 1, k); for (int j = 0; j < amount; j++) { weight.push_back(w); profit.push_back(v); } } n = weight.size(); vector<vector<ll>> dp(s+1, vector<ll>(n, 0)); for (ll w = 1; w <= s; w++) { for (int i = 1; i < n; i++) { dp[w][i] = dp[w][i-1]; if (w-weight[i] >= 0) { dp[w][i] = max(dp[w][i], profit[i] + dp[w-weight[i]][i-1]); } } } cout << dp[s][n-1] << 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...