Submission #70779984

---

Source Code Expand

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define int long long
#define ALL(x) (x).begin(), (x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

typedef pair<int, int> PI;
typedef pair<int, pair<int, int>> PII;
static const int INF = 1010000000000000017LL;
static const double eps = 1e-12;
static const double pi = 3.14159265358979323846;
static const int dx[4] = {1, -1, 0, 0};
static const int dy[4] = {0, 0, 1, -1};
static const int ddx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
static const int ddy[8] = {0, 0, 1, -1, 1, -1, 1, -1};

template <class T>
inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int MAX_W = 250000;

int N;

signed main() {
    cin >> N;
    vector<int> W(N), H(N), B(N);
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        cin >> W[i] >> H[i] >> B[i];
        sum += W[i];
    }
    vector<vector<int>> dp(N, vector<int>(MAX_W + 1, 0));
    dp[0][W[0]] = H[0];
    dp[0][0] = B[0];
    for (int i = 0; i < N - 1; ++i) {
        for (int j = 0; j <= MAX_W; ++j) {
            // 頭につける
            if (j + W[i + 1] <= MAX_W) {
                chmax(dp[i + 1][j + W[i + 1]], dp[i][j] + H[i + 1]);
            }
            chmax(dp[i + 1][j], dp[i][j] + B[i + 1]);
        }
    }
    int ans = 0;
    for (int i = 0; i <= MAX_W; ++i) {
        int b_w = sum - i;
        if (i <= b_w) {
            chmax(ans, dp[N - 1][i]);
        }
    }
    cout << ans << endl;
}

Submission Info

Judge Result