Submission #1171514

#TimeUsernameProblemLanguageResultExecution timeMemory
1171514abcsedafaefKnapsack (NOI18_knapsack)C++20
49 / 100
246 ms1236 KiB
#include <bits/stdc++.h> using namespace std; #define vi vector<int> #define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL) void solve() { int x, n; cin >> x >> n; vi v_temp, c_temp, t_temp; for (int i = 0; i < n; i++) { int value, weight, amt; cin >> value >> weight >> amt; if (weight <= x && amt > 0) { v_temp.push_back(value); c_temp.push_back(weight); t_temp.push_back(amt); } } n = v_temp.size(); if(n == 0) { cout << 0; return; } vi v = v_temp, c = c_temp, t = t_temp; if(n == 1) { int maxCopies = min(t[0], x / c[0]); cout << maxCopies * v[0]; return; } vector<vi> dp(n + 1, vi(x + 1, 0)); for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= x; j++) { int skip = dp[i + 1][j]; dp[i][j] = skip; for (int k = 1; k <= t[i]; k++) { if (j - k * c[i] >= 0) { int pick = k * v[i] + dp[i + 1][j - k * c[i]]; dp[i][j] = max(dp[i][j], pick); } } } } cout << dp[0][x]; } int main() { fast_io; 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...