結果

問題 No.2741 Balanced Choice
ユーザー Yusuke.TYusuke.T
提出日時 2024-04-20 14:27:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 142 ms / 2,000 ms
コード長 3,473 bytes
コンパイル時間 1,402 ms
コンパイル使用メモリ 126,864 KB
実行使用メモリ 101,376 KB
最終ジャッジ日時 2024-10-12 10:00:24
合計ジャッジ時間 3,687 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 130 ms
101,248 KB
testcase_01 AC 132 ms
101,248 KB
testcase_02 AC 137 ms
101,248 KB
testcase_03 AC 142 ms
101,248 KB
testcase_04 AC 140 ms
101,248 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 105 ms
101,248 KB
testcase_08 AC 120 ms
101,248 KB
testcase_09 AC 103 ms
101,248 KB
testcase_10 AC 110 ms
101,376 KB
testcase_11 AC 120 ms
101,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>

constexpr int MAX_INT = 2147483647;
constexpr int MIN_INT = -2147483648;

#define rep(n, a, b) for (int (n) = (a); (n) < (b); (n)++)
#define rrep(n, a, b) for (int (n) = (a); (n) >= (b); (n)--)
#define llrep(n, a, b) for (long long (n) = (a); (n) < (b); (n)++)
#define llrrep(n, a, b) for (long long (n) = (a); (n) >= (b); (n)--)
#define itrAll(x) (x).begin(), (x).end()
#define inputvec(v) for (auto& x : v) {std::cin >> x;}
using namespace std;

using uint = unsigned int;
using ushort = unsigned short;
using byte = unsigned char;
using ll = long long;
using ull = unsigned long long;
using ldouble = long double;
using ipair = pair<int, int>;
using llpair = pair<long long, long long>;

template<typename T>
void chmin(T& v1, T v2) {
	if (v1 > v2) v1 = v2;
}

template<typename T>
void chmax(T& v1, T v2) {
	if (v1 < v2) v1 = v2;
}

int main() {
    int N, W, D;
    cin >> N >> W>> D;

    int c0 = 0, c1 = 0;
    vector<pair<int, int>> wv0(N), wv1(N);

    rep(i, 0, N) {
        int ti;
        cin >> ti;

        if (!ti) {
            cin >> wv0[c0].first >> wv0[c0].second;
            c0++;
        }
        else {
            cin >> wv1[c1].first >> wv1[c1].second;
            c1++;
        }
    }

    wv0.resize(c0);
    wv1.resize(c1);

    vector<vector<int>> max0(c0 + 1, vector<int>(5001)), max1(c1 + 1, vector<int>(5001)); // [i][w] := i 番目までの中からいくつか選んで, 総重量を w にしたときの価値の最大値

    rep(i, 0, c0) max0[i + 1][wv0[i].first] = wv0[i].second;
    rep(i, 0, c1) max1[i + 1][wv1[i].first] = wv1[i].second;

    // dp1
    for (int i = 1; i <= c0; i++) {
        auto& wv = wv0[i - 1];
        for (int w = 1; w <= W; w++) {
            int whenNotUsed = max0[i - 1][w];
            int whenUsed = (w >= wv.first) ? max0[i - 1][w - wv.first] : 0;

            if (whenNotUsed) {
                if (whenUsed) chmax(max0[i][w], max(whenNotUsed, whenUsed + wv.second));
                else chmax(max0[i][w], whenNotUsed);
            }
            else if (whenUsed) {
                chmax(max0[i][w], whenUsed + wv.second);
            }
        }
    }

    // dp2
    for (int i = 1; i <= c1; i++) {
        auto& wv = wv1[i - 1];
        for (int w = 1; w <= W; w++) {
            int whenNotUsed = max1[i - 1][w];
            int whenUsed = (w >= wv.first) ? max1[i - 1][w - wv.first] : 0;

            if (whenNotUsed) {
                if (whenUsed) chmax(max1[i][w], max(whenNotUsed, whenUsed + wv.second));
                else chmax(max1[i][w], whenNotUsed);
            }
            else if (whenUsed) {
                chmax(max1[i][w], whenUsed + wv.second);
            }
        }
    }

    int ans = 0;

    for (int d = 0; d <= D; d++) {
        chmax(ans, max(max0[c0][d], max1[c1][d]));

        for (int w0 = 1; (w0 << 1) + d <= W; w0++) {
            int m0 = max0[c0][w0];
            int m1 = max1[c1][w0 + d];
            if ((ll)m0 * m1) chmax(ans, m0 + m1);
        }
        for (int w1 = 1; (w1 << 1) + d <= W; w1++) {
            int m0 = max0[c0][w1 + d];
            int m1 = max1[c1][w1];
            if ((ll)m0 * m1) chmax(ans, m0 + m1);;
        }
    }

    cout << ans << endl;
    return 0;
}
0