結果
問題 | No.2026 Yet Another Knapsack Problem |
ユーザー |
|
提出日時 | 2022-04-22 02:55:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,802 ms / 10,000 ms |
コード長 | 1,724 bytes |
コンパイル時間 | 988 ms |
コンパイル使用メモリ | 101,580 KB |
最終ジャッジ日時 | 2025-01-28 19:34:34 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
// TLE? Θ(N^2(logN)^2) (using segment tree)#include <algorithm>#include <cassert>#include <deque>#include <iostream>#include <limits>#include <vector>#include <atcoder/segtree>constexpr int64_t inf = std::numeric_limits<int64_t>::max() / 2;int64_t op(int64_t x, int64_t y) {return std::max(x, y);}int64_t e() {return -inf;}int main() {int n;std::cin >> n;std::vector<int32_t> c(n + 1);std::vector<int64_t> v(n + 1);for (int i = 1; i <= n; ++i) {std::cin >> c[i] >> v[i];}std::vector dp(n + 1, std::vector<int64_t>(n + 1, -inf));dp[0][0] = 0;for (int32_t i = n; i > 0; --i) {const int32_t max_num = std::min(n, n / i);const int32_t max_sum = n;// dp[num][sum] = max{ pd[num-p][sum-p*i]-(num-p)*v[i] | 0<=p<=c[i] } ⋃ {-∞} + num*v[i]for (int32_t num = 0; num <= max_num; ++num) {const int32_t sum_r = num ? i - 1 : max_sum;for (int32_t sum = 0; sum <= sum_r; ++sum) {const int32_t max_p = std::min(max_num - num, (max_sum - sum) / i);std::vector<int64_t> init(max_p + 1);for (int32_t p = 0; p <= max_p; ++p) {init[p] = dp[num + p][sum + i * p] - (num + p) * v[i];}atcoder::segtree<int64_t, op, e> seg(std::move(init));for (int32_t p = 0; p <= max_p; ++p) {dp[num + p][sum + i * p] = seg.prod(std::max(0, p - c[i]), p + 1) + (num + p) * v[i];}}}}for (int32_t k = 1; k <= n; ++k) {std::cout << *std::max_element(dp[k].begin(), dp[k].end()) << '\n';}return 0;}