제출 #1306083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306083		marctg	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	572 KiB

knapsack

#include <iostream>

using namespace std;

struct ura{
    int v, w, k;
}v[100001];

int dp[10001];

int main()
{
    int s, n;
    cin >> s >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i].v >> v[i].w >> v[i].k;
        if(v[i].w > s){
            i--;
            n--;
        }
    }
    bool flag = true;
    while(flag){
        flag = false;
        for(int i = 1; i <= n; i++){
            if(v[i].k >= 3){
                n++;
                v[n].v = v[i].v;
                v[n].w = v[i].w;
                v[n].k = v[i].k / 3;
                v[i].k = v[i].k % 3;
                flag = true;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = s; j >= 1; j--){
            for(int k = 1; k <= v[i].k; k++){
                if(j + (k * v[i].w) <= s){
                    dp[j + (k * v[i].w)] = max(dp[j + (k * v[i].w)], dp[j] + (k * v[i].v));
                }
            }
        }
    }
    cout << dp[s] << "\n";
    return 0;
}

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