Submission #976733

#	Time	Username	Problem	Language	Result	Execution time	Memory
976733		vjudge1	Knapsack (NOI18_knapsack)	C++17	0 / 100	112 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define debug cout << "here\n";

#define ll long long

long long ans = 0;
ll v[1000003], w[1000003],k[1000003];
ll dp[2002][100003];

long long ns(int s, int idx){
    if(s==0 || idx == 0)return 0;
    else if(dp[s][idx] != -1) return dp[s][idx];

    ll res = 0;
    for(int i = 1; i <= k[idx]; i++){
        if(s >= w[idx] * i)
            res = max(res, ns(s-w[idx] * i, idx-1) + v[idx] * i);
        else break;
    }
    res = max(res, ns(s,idx-1));
    dp[s][idx] = res;
    return res;
}

int main()
{
    memset(dp,-1,sizeof(dp));
    int s,n;
    cin >> s>> n;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> k[i];
    cout << ns(s,n);
    return 0;
}

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