제출 #1266854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266854		Balsa	Knapsack (NOI18_knapsack)	C++20	73 / 100	151 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
    ll S, n;
    cin >> S >> n;

    vector<ll> V(n+1), W(n+1), K(n+1);
    for (ll i = 1; i <= n; i++) {
        cin >> V[i] >> W[i] >> K[i];
        K[i] = min(K[i], 2000LL);
    }

    vector<vector<ll>> dp(n+1, vector<ll>(S+1, 0));

    for (ll i = 1; i <= n; i++) {
        for (ll w = 1; w <= S; w++) {

            for (ll j = 0; j <= K[i]; j++) {
                if (w - j*W[i] < 0) break;
                dp[i][w] = max(dp[i][w], dp[i-1][w-j*W[i]] + j*V[i]);
            }
        }
    }

    
    // for (ll i = 0; i <= n; i++) {
    //     for (ll w = 0; w <= S; w++) {
    //         cout << dp[i][w] << ' ';
    //     }
    //     cout << '\n';
    // }

    cout << *max_element(dp[n].begin(), dp[n].end()) << '\n';
}

int main() {
    // freopen("cowmbat.in", "r", stdin);
    // freopen("cowmbat.out", "w", stdout);

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27