제출 #1171720

#제출 시각아이디문제언어결과실행 시간메모리
1171720abcsedafaefKnapsack (NOI18_knapsack)C++20
100 / 100
130 ms175684 KiB
#include <bits/stdc++.h> using namespace std; #define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL) #define ll long long typedef pair<ll, pair<ll, ll>> item; void solve() { ll x, n; cin >> x >> n; vector<item> items; for (ll i = 0; i < n; i++) { ll 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) { ll maxCopies = min(items[0].second.second, x / items[0].second.first); cout << maxCopies * items[0].first; return; } vector<item> new_item; map<ll, ll> myMap; for (item it: items) { if (myMap[it.second.first] * it.second.first > x) continue; myMap[it.second.first] += it.second.second; new_item.push_back(it); } n = new_item.size(); vector<vector<ll>> dp(n + 1, vector<ll>(x + 1, 0)); for (ll i = n - 1; i >= 0; i--) { for (ll j = 0; j <= x; j++) { ll skip = dp[i + 1][j]; dp[i][j] = skip; for (ll k = 1; k <= new_item[i].second.second && k*new_item[i].second.first<=j ; k++) { if (j - k * new_item[i].second.first >= 0) { ll 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; }
#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...