Submission #1151331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151331		jeffff	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	15944 KiB

knapsack

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

struct p{
    long long v, w;
} c[3000010];

long long S, N, v, w, k, n1 = 1, f[20001];


int main () {
    cin >> S >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> v >> w >> k;
        int t = 1;
        while (k >= t){
            c[++n1].v = v*t;
            c[n1].w = w*t;
            k -= t;
            t *= 2;
        }
        if (k > 0) {
            c[++n1].v = v*k;
            c[n1].w = w*k;
        }
    }
    for (int i = 1; i <= n1; ++i) {
        for (int j = S; j >= c[i].w; --j) {
            f[j] = max(f[j], f[j - c[i].w] + c[i].v);
        }
    }
    cout << f[S];
}

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