結果
問題 | No.2617 容量3のナップザック |
ユーザー | Kude |
提出日時 | 2024-01-26 22:16:09 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 312 ms / 2,000 ms |
コード長 | 3,818 bytes |
コンパイル時間 | 3,550 ms |
コンパイル使用メモリ | 288,028 KB |
実行使用メモリ | 31,696 KB |
最終ジャッジ日時 | 2024-01-26 22:16:22 |
合計ジャッジ時間 | 10,020 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 2 ms
6,548 KB |
testcase_02 | AC | 2 ms
6,548 KB |
testcase_03 | AC | 2 ms
6,548 KB |
testcase_04 | AC | 2 ms
6,548 KB |
testcase_05 | AC | 2 ms
6,548 KB |
testcase_06 | AC | 1 ms
6,548 KB |
testcase_07 | AC | 2 ms
6,548 KB |
testcase_08 | AC | 2 ms
6,548 KB |
testcase_09 | AC | 2 ms
6,548 KB |
testcase_10 | AC | 2 ms
6,548 KB |
testcase_11 | AC | 2 ms
6,548 KB |
testcase_12 | AC | 277 ms
21,744 KB |
testcase_13 | AC | 162 ms
20,740 KB |
testcase_14 | AC | 262 ms
21,600 KB |
testcase_15 | AC | 124 ms
14,056 KB |
testcase_16 | AC | 103 ms
13,284 KB |
testcase_17 | AC | 213 ms
16,920 KB |
testcase_18 | AC | 180 ms
18,024 KB |
testcase_19 | AC | 35 ms
6,548 KB |
testcase_20 | AC | 151 ms
19,444 KB |
testcase_21 | AC | 128 ms
11,968 KB |
testcase_22 | AC | 173 ms
21,012 KB |
testcase_23 | AC | 264 ms
21,252 KB |
testcase_24 | AC | 8 ms
6,548 KB |
testcase_25 | AC | 85 ms
13,808 KB |
testcase_26 | AC | 109 ms
13,828 KB |
testcase_27 | AC | 99 ms
10,228 KB |
testcase_28 | AC | 8 ms
6,548 KB |
testcase_29 | AC | 59 ms
8,640 KB |
testcase_30 | AC | 197 ms
19,884 KB |
testcase_31 | AC | 239 ms
17,000 KB |
testcase_32 | AC | 230 ms
22,196 KB |
testcase_33 | AC | 269 ms
21,940 KB |
testcase_34 | AC | 312 ms
24,224 KB |
testcase_35 | AC | 266 ms
22,068 KB |
testcase_36 | AC | 199 ms
22,580 KB |
testcase_37 | AC | 310 ms
24,196 KB |
testcase_38 | AC | 187 ms
22,452 KB |
testcase_39 | AC | 158 ms
21,292 KB |
testcase_40 | AC | 267 ms
21,940 KB |
testcase_41 | AC | 147 ms
31,696 KB |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; // https://ei1333.github.io/library/structure/others/priority-sum-structure.hpp template< 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() { ios::sync_with_stdio(false); cin.tie(0); int n, k, seed, a, b, m; cin >> n >> k >> seed >> a >> b >> m; VI f(2 * n); rep(i, 2 * n) { f[i] = seed; seed = ((ll)a * seed + b) % m; } VI v1, v2, v3; rep(i, n) { int wi = f[i] % 3; int vi = f[n + i]; (wi == 0 ? v1 : wi == 1 ? v2 : v3).emplace_back(vi); } sort(rall(v1)); sort(rall(v2)); sort(rall(v3)); ll ans = 0; rep(r, 3) { int now = min(k, (int)v2.size()); if (now < r) continue; while (now % 3 != r) now--; ll sm2 = 0; rep(i, now) { if (i < ssize(v1)) sm2 += v1[i] + 2LL * v2[i]; else sm2 += 2LL * v2[i]; } MaximumSum<long long> q(k - now); for (auto x : v3) q.insert(3LL * x); for (int i = now; i < ssize(v1); i += 3) { int j = min<int>(i + 3, ssize(v1)); q.insert(accumulate(v1.begin() + i, v1.begin() + j, 0LL)); } chmax<ll>(ans, sm2 + q.query()); while (now != r) { now -= 3; for (int i = now; i < now + 3; i++) { if (i < ssize(v1)) sm2 -= v1[i] + 2LL * v2[i]; else sm2 -= 2LL * v2[i]; } if (now < ssize(v1)) { int j = min<int>(now + 3, ssize(v1)); q.insert(accumulate(v1.begin() + now, v1.begin() + j, 0LL)); } q.set_k(k - now); chmax<ll>(ans, sm2 + q.query()); } } cout << ans << '\n'; }