제출 #916207

#제출 시각아이디문제언어결과실행 시간메모리
916207lamterKnapsack (NOI18_knapsack)C++17
73 / 100
1048 ms1500 KiB
#include <bits/stdc++.h> const int M = 2000; std::vector <std::pair <int, int>> items[M + 1]; long long int dp[M + 1]; int main(void) { std::ios_base::sync_with_stdio(0); std::cin.tie(nullptr); int S, n; std::cin >> S >> n; for (int i = 0; i < n; i += 1) { int v, w, k; std::cin >> v >> w >> k; items[w].emplace_back(v, std::min(k, S / w)); } for (int w = 1; w <= S; w += 1) { std::sort(items[w].begin(), items[w].end(), std::greater <> ()); for (const auto& [v, cnt] : items[w]) { int total = 0; for (int i = 1; i <= cnt and total <= S; i += 1) { for (int t = S; t >= w; t -= 1) dp[t] = std::max(dp[t], dp[t - w] + v); total += w; } } } std::cout << dp[S] << '\n'; return 0^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...