結果

問題 No.2617 容量3のナップザック
ユーザー startcppstartcpp
提出日時 2022-02-05 19:26:45
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 192 ms / 2,000 ms
コード長 4,354 bytes
コンパイル時間 1,057 ms
コンパイル使用メモリ 93,792 KB
実行使用メモリ 60,312 KB
最終ジャッジ日時 2023-12-21 23:41:15
合計ジャッジ時間 6,009 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 1 ms
6,676 KB
testcase_03 AC 1 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 1 ms
6,676 KB
testcase_07 AC 2 ms
6,676 KB
testcase_08 AC 2 ms
6,676 KB
testcase_09 AC 2 ms
6,676 KB
testcase_10 AC 2 ms
6,676 KB
testcase_11 AC 2 ms
6,676 KB
testcase_12 AC 143 ms
44,572 KB
testcase_13 AC 139 ms
52,488 KB
testcase_14 AC 137 ms
42,988 KB
testcase_15 AC 95 ms
35,608 KB
testcase_16 AC 98 ms
32,344 KB
testcase_17 AC 131 ms
41,312 KB
testcase_18 AC 122 ms
41,676 KB
testcase_19 AC 20 ms
9,972 KB
testcase_20 AC 126 ms
48,944 KB
testcase_21 AC 70 ms
23,720 KB
testcase_22 AC 143 ms
53,480 KB
testcase_23 AC 190 ms
53,728 KB
testcase_24 AC 9 ms
6,676 KB
testcase_25 AC 87 ms
34,556 KB
testcase_26 AC 106 ms
34,192 KB
testcase_27 AC 57 ms
19,820 KB
testcase_28 AC 7 ms
6,676 KB
testcase_29 AC 54 ms
21,936 KB
testcase_30 AC 133 ms
50,240 KB
testcase_31 AC 129 ms
40,464 KB
testcase_32 AC 160 ms
59,416 KB
testcase_33 AC 179 ms
60,180 KB
testcase_34 AC 192 ms
59,224 KB
testcase_35 AC 171 ms
59,368 KB
testcase_36 AC 189 ms
60,312 KB
testcase_37 AC 192 ms
59,416 KB
testcase_38 AC 159 ms
60,176 KB
testcase_39 AC 152 ms
58,188 KB
testcase_40 AC 177 ms
59,932 KB
testcase_41 AC 77 ms
58,188 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <random>
#include <cassert>
#define int long long
using namespace std;


mt19937 mt(7623765);


class TestCase {
public:
	int N, K, seed, a, b, m;
	vector<int> f, w, v;
	vector<int> values[4];	//values[weight] = 価値リスト

private:
	bool is_valid() {
		if (N <= 0 || N > 1000000) return false;
		if (K <= 0 || K > N) return false;
		if (m <= 2 || m > 1000000000) return false;
		if (a <= 0 || a >= m) return false;
		if (b <= 0 || b >= m) return false;
		if (seed <= 0 || seed >= m) return false;
		return true;
	}

	void generate_fwv() {
		f.resize(2 * N);
		f[0] = seed;
		for (int i = 1; i < 2 * N; i++) {
			f[i] = (a * f[i - 1] + b) % m;
		}

		w.resize(N);
		for (int i = 0; i < N; i++) {
			w[i] = f[i] % 3 + 1;
		}

		v.resize(N);
		for (int i = 0; i < N; i++) {
			v[i] = w[i] * f[N + i];
		}
	}

	void generate_values() {
		for (int i = 0; i < N; i++) {
			values[w[i]].push_back(v[i]);
		}
	}

public:
	void input() {
		cin >> N >> K >> seed >> a >> b >> m;
		assert(is_valid());
		generate_fwv();
		generate_values();
	}

	void generate(int N) {
		this->N = N;
		K = mt() % N + 1;
		m = mt() % 999999998 + 3;
		a = mt() % (m - 1) + 1;
		b = mt() % (m - 1) + 1;
		seed = mt() % (m - 1) + 1;
		assert(is_valid());
		generate_fwv();
		generate_values();
	}

	void print() {
		printf("N = %lld, K = %lld, seed = %lld, a = %lld, b = %lld, m = %lld\n", N, K, seed, a, b, m);
		for (int i = 1; i <= 3; i++) {
			for (int j = 0; j < values[i].size(); j++) {
				cout << values[i][j];
				if (j + 1 < values[i].size()) cout << " ";
			}
			cout << endl;
		}
	}
};


class Solver {
protected:
	int N, K;
	vector<int> values[4];

	void input(TestCase &testcase) {
		N = testcase.N;
		K = testcase.K;
		for (int i = 0; i < 4; i++) {
			values[i] = testcase.values[i];
		}
	}

public:
	virtual int solve(TestCase &testcase) = 0;
};


class NaiveSolver : public Solver {
public:
	int solve(TestCase &testcase) {
		input(testcase);

		for (int i = 1; i <= 3; i++) {
			sort(values[i].begin(), values[i].end(), greater<int>());
		}

		vector<int> sum_values[4];	//sum_values[weight][count] = 重さ合計
		for (int i = 1; i <= 3; i++) {
			sum_values[i].resize(values[i].size() + 1);
			sum_values[i][0] = 0;
			for (int j = 0; j < values[i].size(); j++) {
				sum_values[i][j + 1] = sum_values[i][j] + values[i][j];
			}
		}

		int ans = 0;
		for (int i = 0; i <= values[1].size(); i++) {
			for (int j = 0; j <= values[2].size(); j++) {
				for (int k = 0; k <= values[3].size(); k++) {
					int box_count = k + j + (max(0LL, i - j) + 2) / 3;
					if (box_count <= K) {
						ans = max(ans, sum_values[1][i] + sum_values[2][j] + sum_values[3][k]);
					}
				}
			}
		}
		return ans;
	}
};

class FastSolver : public Solver {
	vector<int> sum_values[4];

	int sum_values_func(int weight, int cnt) {
		if (cnt < sum_values[weight].size()) {
			return sum_values[weight][cnt];
		}
		return sum_values[weight][values[weight].size()];
	}

	//重さ2をx個使うとしたとき、重さ1, 2の荷物を容量3のナップザックに詰めるときの価値和のmaxは？
	int f(int x, int i) {
		return sum_values[2][i] + sum_values_func(1, 3 * x - 2 * i);
	}

	//重さ1, 2の荷物を、容量3のナップザックx個に詰めるときの、詰める荷物の価値和の最大値
	int f(int x) {
		//f(x, i + 1) - f(x, i) <= 0になる最小のiは？0 <= i < c_2, 無ければc_2.
		int c_2 = min(x, (int)values[2].size());
		int ng = -1, ok = c_2, mid;	//(ng, ok]
		while (ok - ng >= 2) {
			mid = (ng + ok) / 2;
			if (f(x, mid + 1) - f(x, mid) <= 0) {
				ok = mid;
			}
			else {
				ng = mid;
			}
		}
		return f(x, ok);
	}

public:
	int solve(TestCase &testcase) {
		input(testcase);

		for (int i = 1; i <= 3; i++) {
			sort(values[i].begin(), values[i].end(), greater<int>());
			sum_values[i].resize(values[i].size() + 1);
			sum_values[i][0] = 0;
			for (int j = 0; j < values[i].size(); j++) {
				sum_values[i][j + 1] = sum_values[i][j] + values[i][j];
			}
		}

		int ans = 0;
		for (int i = 0; i <= min(K, (int)values[3].size()); i++) { //重さ3をi個使う
			int res = sum_values[3][i] + f(K - i);
			ans = max(ans, res);
		}
		return ans;
	}
};

FastSolver fast;

signed main() {
	TestCase test;
	test.input();
	cout << fast.solve(test) << endl;
	return 0;
}
0