Submission #1192187

#TimeUsernameProblemLanguageResultExecution timeMemory
1192187mahadKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms2632 KiB
#include <bits/stdc++.h> using namespace std; #define int long long void solve() { int s, n; cin >> s >> n; vector<int> values(n); vector<int> weights(n); vector<int> copies(n); for (int i = 0; i < n; i++) { cin >> values[i] >> weights[i] >> copies[i]; copies[i] = min(copies[i], s); } vector<int> dp(s+5, -1); dp[0] = 0; vector<vector<int>> mod_table(s+1); for (int i = 0; i < n; i++) { for (int j = s-weights[i]; j >= 0; j--) { if (dp[j] != -1) { for (int k = 0; k < copies[i] && j + (k+1)*weights[i] <= s; k++) { dp[j+(k+1)*weights[i]] = max(dp[j+(k+1)*weights[i]], dp[j] + (k+1)*values[i]); } } } } int ans = *max_element(dp.begin(), dp.end()); cout << ans << "\n"; }; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); 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...