제출 #633109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633109		a_aguilo	Knapsack (NOI18_knapsack)	C++14	73 / 100	870 ms	262144 KiB

knapsack

#include<bits/stdc++.h>

using namespace std;

typedef vector<long long int> vi;
typedef vector<vi> vvi;

vvi dp;
vi values, weight, freqs;

int S, N;

long long int money(int wLeft, int item){
    if(item < 0) return 0;
    if(dp[wLeft][item] != -1) return dp[wLeft][item];
    dp[wLeft][item] = money(wLeft, item-1);
    for(int reps = 1; reps <= freqs[item]; ++reps){
        if((long long)weight[item]*reps <= (long long)wLeft) dp[wLeft][item] = max(dp[wLeft][item], (long long)values[item]*reps + money(wLeft - weight[item]*reps, item-1));
        else break;
    }
    return dp[wLeft][item];
}

int main(){
    cin >> S >> N;
    dp = vvi (S+1, vi(N, -1));
    values = vi(N);
    weight = vi(N);
    freqs = vi(N);
    for(int i = 0; i < N; ++i) cin >> values[i] >> weight[i] >> freqs[i];
    cout << money(S, N-1) << endl;
    return 0;
}

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