Submission #719068

#	Time	Username	Problem	Language	Result	Execution time	Memory
719068		lalig777	Knapsack (NOI18_knapsack)	C++14	73 / 100	198 ms	262144 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    int n, w, a, b, c;
    cin>>w>>n;
    vector<vector<long long int>>dp(n+1, vector<long long int>(w+1));
    for (int i=1; i<=n; i++){
        dp[i]=dp[i-1];
        cin>>a>>b>>c;
        for (int j=0; j<=w; j++){
            for (int k=1; k<=c; k++){
                if (b*k<=j) dp[i][j]=max(dp[i][j], dp[i-1][j-b*k]+a*k);
                else break;
            }
        }
    }cout<<dp[n][w];
    return 0;
}

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