Submission #1005469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005469		kvintsekstakord	Knapsack (NOI18_knapsack)	C++17	37 / 100	4 ms	16220 KiB

knapsack

#include <bits/stdc++.h>
#define int int64_t
using namespace std;

int S, N;

int w[1010];
int v[1010];

int dp[2010][1010];

int32_t main()
{
    cin >> S >> N;
    int pos = 1;
    for(int i = 1; i <= N; i++){
        int vi, wi, ki; cin >> vi >> wi >> ki;
        int j;
        for(j = pos; j < pos+ki; j++){
            w[j]=wi;
            v[j]=vi;
        }
        pos = j;
    }


    for(int i = 0; i <= pos; i++) dp[0][i]=0;
    for(int i = 0; i <= S; i++) dp[i][0]=0;

    for(int i = 1; i <= S; i++){
        for(int j = 1; j < pos; j++){
            if(i-w[j]<0) dp[i][j]=dp[i][j-1];
            else{
                dp[i][j]=max(dp[i][j-1], dp[i-w[j]][j-1]+v[j]);
            }
        }
    }
    cout << dp[S][pos-1];
    return 0;
}

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