Submission #1171714

#TimeUsernameProblemLanguageResultExecution timeMemory
1171714abcsedafaefKnapsack (NOI18_knapsack)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define fast_io \ ios_base::sync_with_stdio(false); \ cin.tie(NULL) typedef pair<int, pair<int, int>> item; void solve() { int x, n; cin >> x >> n; vector<item> items; for (int i = 0; i < n; i++) { int value, weight, amt; cin >> value >> weight >> amt; if (weight <= x && amt > 0) { items.push_back({value, {weight, amt}}); } } sort(items.begin(), items.end(), [](const item &a, const item &b) { if (a.first != b.first) return a.first > b.first; return a.second.first < b.second.first; }); n = items.size(); if (n == 0) { cout << 0; return; } if (n == 1) { int maxCopies = min(items[0].second.second, x / items[0].second.first); cout << maxCopies * items[0].first; return; } vi new_item; map<int,int> myMap; for (item item: items) { if (myMap[item.second.first] * item.second.first > S) { continue; } myMap[item.second.first] += item.second.second; new_item.push_back(item); } // swap(new_item, items); vector<vector<int>> dp(n + 1, vector<int>(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 <= new_item[i].second.second; k++) { if (j - k * new_item[i].second.first >= 0) { int pick = k * new_item[i].first + dp[i + 1][j - k * new_item[i].second.first]; dp[i][j] = max(dp[i][j], pick); } } } } cout << dp[0][x]; } int main() { fast_io; solve(); return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:43:5: error: 'vi' was not declared in this scope
   43 |     vi new_item;
      |     ^~
knapsack.cpp:46:60: error: 'S' was not declared in this scope
   46 |         if (myMap[item.second.first] * item.second.first > S) {
      |                                                            ^
knapsack.cpp:50:9: error: 'new_item' was not declared in this scope
   50 |         new_item.push_back(item);
      |         ^~~~~~~~
knapsack.cpp:60:34: error: 'new_item' was not declared in this scope
   60 |             for (int k = 1; k <= new_item[i].second.second; k++)
      |                                  ^~~~~~~~