Submission #1171707

#TimeUsernameProblemLanguageResultExecution timeMemory
1171707abcsedafaefKnapsack (NOI18_knapsack)C++20
12 / 100
0 ms328 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; vector<int> new_t; map<int, int> myMap; // Track total count for each weight for (int i = 0; i < n; i++) { int value, weight, amt; cin >> value >> weight >> amt; v_temp.push_back(value); c_temp.push_back(weight); t_temp.push_back(amt); } vi v, c, t; for (int i = 0; i < n; i++) { if (myMap[c_temp[i]] * c_temp[i] > x) { // Skip if weight class already exceeds capacity continue; } myMap[c_temp[i]] += t_temp[i]; // Add count for this weight v.push_back(v_temp[i]); c.push_back(c_temp[i]); t.push_back(t_temp[i]); } n = v.size(); if (n == 0) { cout << 0; return; } for (int i = 0; i < n; i++) { new_t.push_back(min(t[i], x / c[i])); } 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 = 0; k <= new_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...