#946931 (C++17) No.2617 容量3のナップザック

• 問題: No.2617 容量3のナップザック
• ユーザー: Carpenters-Cat
• 提出日時: 2024-01-27 02:48:36
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,425 bytes
• コンパイル時間: 2,247 ms
• コンパイル使用メモリ: 211,676 KB
• 実行使用メモリ: 33,004 KB
• 最終ジャッジ日時: 2024-09-28 09:29:59
• 合計ジャッジ時間: 6,138 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,944 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	2 ms; 6,944 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	1 ms; 6,944 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	1 ms; 6,940 KB
testcase_08	AC	1 ms; 6,940 KB
testcase_09	WA	-
testcase_10	AC	2 ms; 6,940 KB
testcase_11	AC	2 ms; 6,940 KB
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	74 ms; 15,828 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	AC	7 ms; 6,940 KB
testcase_25	AC	79 ms; 20,976 KB
testcase_26	AC	78 ms; 16,620 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	AC	48 ms; 13,628 KB
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	AC	139 ms; 29,468 KB
testcase_37	WA	-
testcase_38	WA	-
testcase_39	AC	140 ms; 27,248 KB
testcase_40	WA	-
testcase_41	AC	59 ms; 28,048 KB

ソースコード

#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;
}