Submission #1171725

#TimeUsernameProblemLanguageResultExecution timeMemory
1171725abcsedafaefKnapsack (NOI18_knapsack)C++20
29 / 100
3 ms1100 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; if(t[i]*c[i]>x){ continue; } for (int k = 1; k <= t[i] && k*c[i]<=j; 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...