結果
問題 | No.2617 容量3のナップザック |
ユーザー |
![]() |
提出日時 | 2024-01-27 17:16:41 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,759 bytes |
コンパイル時間 | 3,216 ms |
コンパイル使用メモリ | 280,228 KB |
実行使用メモリ | 77,696 KB |
最終ジャッジ日時 | 2024-09-28 09:43:53 |
合計ジャッジ時間 | 25,213 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 9 WA * 31 |
ソースコード
#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace std;using ll = long long;using namespace __gnu_pbds;template <typename T, typename F = less<T>>using nset = tree<T, null_type, F, rb_tree_tag, tree_order_statistics_node_update>;const int mod = 998244353;int N, K;ll V[1010101];int W[1010101];int main(void){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> N >> K;{ll s, a, b, m;cin >> s >> a >> b >> m;for(int i = 0;i < N;i++){W[i] = s % 3 + 1;s = (s * a + b) % m;}for(int i = 0;i < N;i++){V[i] = s * W[i];s = (s * a + b) % m;}}nset<ll, greater<ll>> st[3];for(int i = 0;i < N;i++){st[W[i] - 1].insert(V[i]);}for(int i = 0;i < N;i++){st[0].insert(0);}ll ans = 0;for(int i = 0;i < K;i++){vector<ll> a;a.push_back((st[0].size() < 3 ? 0 : *st[0].find_by_order(0) + *st[0].find_by_order(1) + *st[0].find_by_order(2)));a.push_back((st[0].empty() || st[1].empty() ? 0 : *st[0].find_by_order(0) + *st[1].find_by_order(0)));a.push_back((st[2].empty() ? 0 : *st[2].find_by_order(0)));int idx = max_element(a.begin(), a.end()) - a.begin();if(a[idx] == 0)break;ans += a[idx];if(idx == 0){st[0].erase(st[0].begin());st[0].erase(st[0].begin());st[0].erase(st[0].begin());}else if(idx == 1){st[0].erase(st[0].begin());st[1].erase(st[1].begin());}else{st[2].erase(st[2].begin());}}cout << ans << endl;return 0;}