Submission #1283580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283580		haithamcoder	Knapsack (NOI18_knapsack)	C++20	12 / 100	2 ms	832 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);
    vector<vector<ll>> weights(s + 1);

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

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

    for (ll i = 0; i < n; i++) {
        sort(weights[i].begin(), weights[i].end(), [&](ll a, ll b) -> bool {
            return v[a] > v[b];
        });
    }

    for (ll i = 1; i <= s; i++) {
        for (ll wt = s - 1; wt >= 0; wt--) {
            ll val = dp[wt];
            ll cnt = 0;
            ll cur_wt = wt;
            for (ll j = 0; j < weights[i].size() && cur_wt + i <= s; j++) {
                for (ll amt = 1; amt <= k[weights[i][j]] && cur_wt + i <= s; amt++) {
                    val += v[weights[i][j]];
                    cur_wt += i;

                    dp[cur_wt] = max(dp[cur_wt], val);
                }
                // ll get = min(k[weights[i][j]], (s - cur_wt) / i);
                // val += v[weights[i][j]] * get;
                // if (i == 1 && wt == 0) {
                //     dbg(get);
                //     dbg(v[weights[i][j]]);
                // } 
                // cur_wt += get * i;

                // dp[cur_wt] = max(dp[cur_wt], val);
            }
        }
    }

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

    // dbg(dp[5]);

    cout << res << "\n";

    return 0;
}

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