結果
問題 | No.2026 Yet Another Knapsack Problem |
ユーザー |
👑 |
提出日時 | 2022-07-29 21:41:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 270 ms / 10,000 ms |
コード長 | 3,352 bytes |
コンパイル時間 | 1,278 ms |
コンパイル使用メモリ | 114,648 KB |
実行使用メモリ | 52,844 KB |
最終ジャッジ日時 | 2024-07-19 14:04:20 |
合計ジャッジ時間 | 4,551 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#pragma GCC optimize ("Ofast")#pragma GCC optimize ("unroll-loops")#include <cassert>#include <cmath>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <functional>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using Int = long long;template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i>= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }// op: T * T -> T, associativetemplate <class T, T (*op)(const T &, const T &)> struct Queue {vector<T> as, aas, bs, bbs;void reserve(int n) {as.reserve(n);aas.reserve(n);bs.reserve(n);bbs.reserve(n);}void reduce() {for (; !bs.empty(); bs.pop_back(), bbs.pop_back()) {as.push_back(bs.back());aas.push_back(aas.empty() ? bs.back() : op(bs.back(), aas.back()));}}T get() {if (as.empty()) reduce();assert(!as.empty());return bbs.empty() ? aas.back() : op(aas.back(), bbs.back());}bool empty() const {return (as.empty() && bs.empty());}int size() const {return as.size() + bs.size();}T front() {if (as.empty()) reduce();assert(!as.empty());return as.back();}void push(const T &t) {bs.push_back(t);bbs.push_back(bbs.empty() ? t : op(bbs.back(), t));}void pop() {if (as.empty()) reduce();assert(!as.empty());as.pop_back();aas.pop_back();}void clear() {as.clear();aas.clear();bs.clear();bbs.clear();}};////////////////////////////////////////////////////////////////////////////////constexpr Int INF = 1001001001001001001LL;int N;vector<int> C;vector<Int> V;Int dp[2510][2510];int main() {for (; ~scanf("%d", &N); ) {C.resize(N + 1);V.resize(N + 1);for (int i = 1; i <= N; ++i) {scanf("%d%lld", &C[i], &V[i]);}for (int k = 0; k <= N; ++k) {fill(dp[k], dp[k] + (N + 1), -INF);}fill(dp[0], dp[0] + (N + 1), 0);for (int i = N; i >= 1; --i) {for (int c = C[i], e = 0; c > 0; ++e) {const int cc = min(c, 1 << e);c -= cc;const int dk = cc;const int dx = cc * i;const Int dv = cc * V[i];for (int k = N / i - dk; k >= 0; --k) {for (int x = 0; x <= N - dx; ++x) {chmax(dp[k + dk][x + dx], dp[k][x] + dv);}}}}for (int k = 1; k <= N; ++k) {printf("%lld\n", dp[k][N]);}#ifdef LOCALcerr<<"========"<<endl;#endif}return 0;}