Submission #1349968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1349968		vjudge1	Knapsack (NOI18_knapsack)	C++17	37 / 100	1095 ms	344 KiB

knapsack

#include <iostream>
using namespace std;

#define int long long

void Knapsack(int n,int W);

int N = 100000, MaxW = 20;

int w[100000+1]; // w???
int v[100000+1]; // v???
int num[100000+1]; // num??
int dp[100000+1];

signed main(){
    cin >> MaxW >> N;

    for (int i = 1; i <= N; i++) {
        cin >> v[i] >> w[i] >> num[i];
    }

    Knapsack(N, MaxW);
    cout << dp[MaxW];
}

void Knapsack(int n,int W){
    for(int i=1;i<=n;i++){ // ??????
        for(int k=0;k<num[i];k++){ // ???????num[i]?
            for(int j=W;j>0;j--){ // ????????
                if(j>=w[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
    }
}

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