結果

問題 No.2617 容量3のナップザック
コンテスト
ユーザー startcpp
提出日時 2022-02-05 19:26:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 4,354 bytes
コンパイル時間 1,153 ms
コンパイル使用メモリ 94,020 KB
実行使用メモリ 61,568 KB
最終ジャッジ日時 2024-09-27 11:10:45
合計ジャッジ時間 5,859 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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