提出 #61749709

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define in(a)                                                                  \
    for (auto &x : a)                                                          \
        cin >> x;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define out(a)                                                                 \
    for (auto x : a)                                                           \
        cout << x << " ";
#define pb push_back
#define int long long
typedef vector<int> vi;
typedef pair<int, int> pii;

void solve()
{
    int n, c;
    cin >> n >> c;
    vector<pair<int, int>> knapsack;
    vector<int> dp(c + 1, 0);
    for (int i = 0; i < n; i++) {
        int weight, value;
        cin >> weight >> value;
        knapsack.push_back({weight, value});
    }

    // so need to find a way to implement take or no take
    // take: means weight reduces while cost increases
    // no take: everything remains the same
    // dp[w] -> store max value possible at weight w
    for (auto [w, v] : knapsack) {
        for (int j = c; j >= 1; j--) {
            if (j - w >= 0) {
                dp[j] = max(dp[j - w] + v, dp[j]);
            }
        }
    }
    cout << dp[c] << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

提出情報

ジャッジ結果