結果
問題 | No.2026 Yet Another Knapsack Problem |
ユーザー |
|
提出日時 | 2022-04-22 03:29:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,112 bytes |
コンパイル時間 | 1,042 ms |
コンパイル使用メモリ | 89,752 KB |
最終ジャッジ日時 | 2025-01-28 19:36:10 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 TLE * 7 |
ソースコード
#include <algorithm>#include <cassert>#include <deque>#include <iostream>#include <limits>#include <vector>template <typename T>struct SlidingWindowMaximum {using value_type = T;SlidingWindowMaximum() {clear();}void push_back(const value_type& v) {while (_dq.size() and _dq.back().first < v) _dq.pop_back();_dq.emplace_back(v, _r++);}void pop_front() {assert(size());if (_dq.front().second == _l++) _dq.pop_front();}value_type query() const {return _dq.front().first;}void clear() {_l = _r = 0;_dq.clear();}int size() const {return _r - _l;}private:std::size_t _l, _r;std::deque<std::pair<value_type, std::size_t>> _dq;};constexpr int64_t inf = std::numeric_limits<int64_t>::max() / 2;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;SlidingWindowMaximum<long long> sw;for (int32_t i = 1; i <= n; ++i) {const int32_t max_num = n;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);sw.clear();for (int32_t p = 0; p <= max_p; ++p) {sw.push_back(dp[num + p][sum + i * p] - (num + p) * v[i]);if (p > c[i]) sw.pop_front();dp[num + p][sum + i * p] = sw.query() + (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;}