Submission #1244442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244442		snowysmo	Knapsack (NOI18_knapsack)	C++20	29 / 100	2 ms	1864 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'

using namespace std;

const ll mx = 1e5+7, inf=-1;
ll s, n;
ll v[mx], w[mx], k[mx];
ll dp[mx][2005];
int main(){
    cin>>s>>n;
    if(n==1){
        ll vv, ww, kk; cin>>vv>>ww>>kk;
        cout<<min(s/ww*vv, kk*vv)<<endl;
        return 0;
    }
    for(ll i=0;i<=n;i++) dp[i][0]=0;
    for(ll i=0;i<=s;i++) dp[0][i]=0;
    for(ll i=1;i<=n;i++) cin>>v[i]>>w[i]>>k[i];
    for(ll j=1;j<=s;j++){
        for(ll i=1;i<=n;i++){
            dp[i][j]=dp[i-1][j];
            ll temp=0;
            if(j-w[i]>=0) temp=dp[i-1][j-w[i]]+v[i];
            dp[i][j]=max(dp[i][j], temp);
        }
    }
    cout<<dp[n][s]<<endl;

    return 0;
}

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