Submission #1264887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264887		marshziin	Knapsack (NOI18_knapsack)	C++20	In queue	0 ms	0 KiB

knapsack

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

#define int long long
#define tii tuple<int,int,int>
bool comp(tii a, tii b) { return get<1>(a) < get<1>(b); } 

const int inf = 1e12 + 10;
const int maxn = 1100;
const int maxw = 5000;
int dp[maxn][maxw];

void solve() {
    int n, s; cin >> s >> n;
    vector<tii> it(n + 1);
    it[0] = {0,0,0}; 
    for (int i = 1; i <= n; i++) {
        int v, w, k; cin >> v >> w >> k;
        it[i] = {v, w, k};
    }
    
    sort(it.begin(), it.end(), comp);
    for (int i = 0; i <= n; i++) 
        for (int j = 0; j <= s; j++)
            dp[i][j] = -inf;
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        int v = get<0>(it[i]), w = get<1>(it[i]), k = get<2>(it[i]);
        for (int j = s; j >= 0; j--) {
            int cur = w, cnt = 1;
            while (cur <= j && cnt <= k) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - cur] + cnt * v);
                cur += w; cnt++;
            }
        }
    }

    int res = 0;
    for (int i = 0; i <= s; i++) {
        res = max(res, dp[n][i]);
    }
    cout << res << '\n';
}

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

    return 0;
}