Submission #1192487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192487		dprto	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	324 KiB

knapsack

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

const int MAX_S = 2005;
long long dp[MAX_S];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int S, N;
    cin >> S >> N;
    
    fill(dp, dp + S + 1, 0);
    
    for (int i = 0; i < N; i++) {
        int w, v, k;
        cin >> w >> v >> k;
        
        if (k * w >= S) {
            for (int s = w; s <= S; s++) {
                if (dp[s - w] != -1) {
                    dp[s] = max(dp[s], dp[s - w] + v);
                }
            }
        } else {
            for (int t = 1; k > 0; t <<= 1) {
                int cnt = min(t, k);
                int cw = cnt * w;
                int cv = cnt * v;
                
                for (int s = S; s >= cw; s--) {
                    dp[s] = max(dp[s], dp[s - cw] + cv);
                }
                
                k -= cnt;
            }
        }
    }

    long long max_value = *max_element(dp, dp + S + 1);
    cout << max_value << endl;
    
    return 0;
}

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