Submission #1283526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283526		haithamcoder	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	2800 KiB

knapsack

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

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;


#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);


int main() {
    Algerian OI

    ll s, n;
    cin >> s >> n;

    vector<ll> k(n), v(n), w(n);

    for (ll i = 0; i < n; i++) {
        cin >> v[i] >> w[i] >> k[i];
    }

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

    for (ll i = 0; i < n; i++) {
        for (ll wt = s - 1; wt >= 0; wt--) {
            for (ll amt = 1; amt <= k[i] && amt * w[i] + wt <= s; amt++) {
                dp[wt + amt * w[i]] = max(dp[wt + amt * w[i]], dp[wt] + amt * v[i]);
            }
        }
    }

    ll res = 0;
    for (ll i = 0; i <= s; i++) res = max(res, dp[i]);

    cout << res << "\n";

    return 0;
}

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