結果

問題 No.2617 容量3のナップザック
ユーザー Carpenters-Cat
提出日時 2024-01-27 02:48:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,425 bytes
コンパイル時間 2,367 ms
コンパイル使用メモリ 204,600 KB
最終ジャッジ日時 2025-02-19 00:05:33
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
	int N, K;
	ll sd, a, b, m;
	cin >> N >> K >> sd >> a >> b >> m;
	std::vector<ll> F(N * 2);
	F[0] = sd;
	for (int i = 1; i < N * 2; i ++) {
		F[i] = (F[i - 1] * a + b) % m;
	}
	vector<ll> V[3];
	for (int i = 0; i < N; i ++) {
		int w = F[i] % 3;
		ll v = F[N + i];
		V[w].push_back(v);
	}
	for (auto& a : V) {
		sort(a.begin(), a.end());
	}
	ll ans = 0;
	ll sm3 = 0;
	queue<ll> que;
	for (int i = 0; i < 3; i ++) {
		if (V[0].empty()) break;
		que.push(V[0].back());
		sm3 += V[0].back();
		V[0].pop_back();
	}
	for (int i = 0; i < K; i ++) {
		ll v1 = sm3, v2 = 0, v3 = 0;
		if (!V[1].empty()) {
			v2 = V[1].back() * 2;
			if (!que.empty()) {
				v2 += que.front();
			}
		}
		if (!V[2].empty()) {
			v3 = V[2].back() * 3;
		}
		ll max_v = max({v1, v2, v3});
		if (max_v == 0) break;
		if (max_v == v3) {
			ans += v3;
			V[2].pop_back();
		} else if (max_v == v2) {
			ans += v2;
			V[1].pop_back();
			if (!que.empty()) {
				sm3 -= que.front();
				que.pop();
				if (!V[0].empty()) {
					sm3 += V[0].back();
					que.push(V[0].back());
					V[0].pop_back();
				}
			}
		} else {
			ans += v1;
			for (int x = 0; x < 3; x ++) {
				if (que.empty()) break;
				sm3 -= que.front();
				que.pop();
				if (!V[0].empty()) {
					sm3 += V[0].back();
					que.push(V[0].back());
					V[0].pop_back();
				}
			}
		}
	}
	cout << ans << endl;
}
0