結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0