結果
問題 | No.2617 容量3のナップザック |
ユーザー |
👑 ![]() |
提出日時 | 2024-01-26 21:55:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 465 ms / 2,000 ms |
コード長 | 3,945 bytes |
コンパイル時間 | 3,970 ms |
コンパイル使用メモリ | 271,736 KB |
実行使用メモリ | 42,024 KB |
最終ジャッジ日時 | 2024-09-28 08:07:08 |
合計ジャッジ時間 | 11,633 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)using ll = long long;constexpr int INF = 0x3f3f3f3f;constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;constexpr double EPS = 1e-8;constexpr int MOD = 998244353;// constexpr int MOD = 1000000007;constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U>inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U>inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << fixed << setprecision(20);}} iosetup;// https://ei1333.github.io/library/structure/others/priority-sum-structure.hpptemplate< typename T, typename Compare = less< T >, typename RCompare = greater< T > >struct PrioritySumStructure {size_t k;T sum;priority_queue< T, vector< T >, Compare > in, d_in;priority_queue< T, vector< T >, RCompare > out, d_out;PrioritySumStructure(int k) : k(k), sum(0) {}void modify() {while(in.size() - d_in.size() < k && !out.empty()) {auto p = out.top();out.pop();if(!d_out.empty() && p == d_out.top()) {d_out.pop();} else {sum += p;in.emplace(p);}}while(in.size() - d_in.size() > k) {auto p = in.top();in.pop();if(!d_in.empty() && p == d_in.top()) {d_in.pop();} else {sum -= p;out.emplace(p);}}while(!d_in.empty() && in.top() == d_in.top()) {in.pop();d_in.pop();}}T query() const {return sum;}void insert(T x) {in.emplace(x);sum += x;modify();}void erase(T x) {assert(size());if(!in.empty() && in.top() == x) {sum -= x;in.pop();} else if(!in.empty() && RCompare()(in.top(), x)) {sum -= x;d_in.emplace(x);} else {d_out.emplace(x);}modify();}void set_k(size_t kk) {k = kk;modify();}size_t get_k() const {return k;}size_t size() const {return in.size() + out.size() - d_in.size() - d_out.size();}};template< typename T >using MaximumSum = PrioritySumStructure< T, greater< T >, less< T > >;template< typename T >using MinimumSum = PrioritySumStructure< T, less< T >, greater< T > >;int main() {int n, k; cin >> n >> k;vector<int> w(n);vector<ll> v(n);{vector<ll> f(n * 2);int a, b, m; cin >> f.front() >> a >> b >> m;FOR(i, 1, n * 2) f[i] = (a * f[i - 1] + b) % m;REP(i, n) w[i] = f[i] % 3 + 1;REP(i, n) v[i] = w[i] * f[i + n];}array<vector<ll>, 4> item{};REP(i, n) item[w[i]].emplace_back(v[i]);FOR(i, 1, 3) ranges::sort(item[i], greater<ll>());ll ans = 0;REP(md, 3) {if (md > k || item[2].size() < md) break;ll cur = 0;REP(i, md) cur += item[2][i] + (i < item[1].size() ? item[1][i] : 0);vector<ll> tmp;tmp.reserve((item[1].size() + 2) / 3);for (int i = md; i < item[1].size(); i += 3) {tmp.emplace_back(0);REP(j, 3) {if (i + j < item[1].size()) tmp.back() += item[1][i + j];}}ranges::reverse(tmp);assert(ranges::is_sorted(tmp));MaximumSum<ll> ms(k - md);for (const ll v_i : tmp) ms.insert(v_i);for (const ll v_i : item[3]) ms.insert(v_i);for (int i = md; i <= k;) {ms.set_k(k - i);chmax(ans, cur + ms.query());if (i >= item[2].size()) break;REP(_, 3) {if (i < item[2].size()) cur += item[2][i];++i;}if (!tmp.empty()) {cur += tmp.back();ms.erase(tmp.back());tmp.pop_back();}}}cout << ans << '\n';return 0;}