Submission #2667169

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 501;

ll dp[N][N][2];

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    ll s, x, ans = 0;
    cin >> n >> s;
    vector<ll> w(n), v(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i] >> v[i];
        if (!i) {
            x = w[0];
        }
        w[i] -= x;
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dp[i][j][0] = -1;
        }
    }
    dp[0][0][0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                dp[i][j][1] = dp[i][j][0];
            }
        }
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k + w[i] < N; ++k) {
                if (dp[j][k][0] == -1) {
                    continue;
                }
                if (k + w[i] <= s - x * (j + 1)) {
                    dp[j + 1][k + w[i]][1] = max(dp[j + 1][k + w[i]][1], dp[j][k][0] + v[i]);
                }
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                dp[i][j][0] = dp[i][j][1];
                ans = max(ans, dp[i][j][0]);
            }
        }
    }
    cout << ans;
    return 0;
}

Submission Info

Judge Result