제출 #798870

#제출 시각아이디문제언어결과실행 시간메모리
798870hoangrealKnapsack (NOI18_knapsack)C++17
73 / 100
269 ms262144 KiB
// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i, a, b) for(ll i = a; i <= b; ++i) #define FOR_NEG(i, a, b) for(ll i = a; i >= b; --i) #define FOR_EACH(a, b) for(auto a : b) ll solve_optimal(ll x, ll n, vector<ll>& weights, vector<ll>& values){ vector<ll> dp(x+1, 0); FOR(i, 1, n) { FOR_NEG(j, x, 1) { ll if_notUse_ans = 0 + dp[j]; ll if_use_ans = 0; if(j - weights[i-1] >= 0) { if_use_ans = values[i-1] + dp[j - weights[i-1]]; } dp[j] = max(if_use_ans, if_notUse_ans); } } return dp[x]; } int main() { // Inputs ll s, n; cin >> s >> n; vector<array<ll, 2>> vk[s + 1]; FOR(i, 0, n-1) { ll vi, wi, ki; cin >> vi >> wi >> ki; vk[wi].push_back({vi, ki}); } // // Pre-processing vector<ll> weights; vector<ll> values; FOR(i, 1, s) { sort(vk[i].rbegin(), vk[i].rend()); // Sort high->low value each weight; for(auto [v, k] : vk[i]) { int max_items_count = min(s / i, k); FOR(j, 1, max_items_count) { weights.push_back(i); values.push_back(v); } } } ll answer; answer = solve_optimal(s, weights.size(), weights, values); cout << answer; 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...