Submission #1264893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264893		marshziin	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	2632 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 maxw = 5000;
int dp[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 = 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[j] = max(dp[j], dp[j - cur] + cnt * v);
                cur += w; cnt++;
            }
        }
    }

    cout << dp[s] << '\n';
}

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

    return 0;
}

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