제출 #1151327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151327		jeffff	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	324 KiB

knapsack

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

struct p{
    int v, w;
} c[300010];

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


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 - 1], f[j - c[i].w] + c[i].v);
        }
    }
    cout << f[S];
}

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