Submission #70776979

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'

using namespace std;

int main() {
    int N;
    cin >> N;
    struct Part { int weight, head, body; };
    vector<Part> parts(N);
    for (int i = 0; i < N; i++) {
        int W, H, B;
        cin >> W >> H >> B;
        parts[i] = { W, H, B };
    }
    const int OFF = 500 * 500 + 10;
    const int MX = 2 * OFF + 10;
    vector<ll> dp(MX, 0);
    vector<vector<bool>> visited(N + 1, vector<bool>(MX, 0));
    visited[0][OFF] = true;
    for (int i = 0; i < N; i++) {
        vector<ll> new_dp(MX, 0);
        for (int w = 0; w < MX; w++) {
            if (!visited[i][w]) continue;
            if (w + parts[i].weight < MX) {
                new_dp[w + parts[i].weight] = max(new_dp[w + parts[i].weight], dp[w] + parts[i].body);
                visited[i + 1][w + parts[i].weight] = true;
            }
            if (w - parts[i].weight >= 0) {
                new_dp[w - parts[i].weight] = max(new_dp[w - parts[i].weight], dp[w] + parts[i].head);
                visited[i + 1][w - parts[i].weight] = true;
            }
        }
        dp.swap(new_dp);
    }
    ll best = 0;
    for (int w = OFF; w < MX; w++) {
        best = max(best, dp[w]);
    }
    cout << best << endl;
    return 0;
}

Submission Info

Judge Result