Submission #1297905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297905		lunarecho	Knapsack (NOI18_knapsack)	C++20	73 / 100	380 ms	2084 KiB

knapsack

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

int n,s;
ll dp[105][2005], v[105], k[105]; 
int w[105];

ll dp_(int i, int wt){
    if(i==0 || wt==0)   
        return 0;
    if(dp[i][wt] != -1)
        return dp[i][wt];
    ll nt = dp_(i-1, wt);
    ll t = 0;
    for(ll j=1;j<=min(k[i], (ll)wt/w[i]);++j) 
        t = max(t, dp_(i-1, wt-j*w[i]) + j * v[i]);
    return dp[i][wt] = max(nt, t);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>s>>n;

    for(int i=1;i<=n;++i) 
        cin>>v[i]>>w[i]>>k[i];

    memset(dp,-1,sizeof(dp));

    cout<<dp_(n,s);

    return 0;
}

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