Submission #720897

#	Time	Username	Problem	Language	Result	Execution time	Memory
720897		lalig777	Knapsack (NOI18_knapsack)	C++14	29 / 100	3 ms	1876 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;
        int ant=1;
        for (int j=1; j<=w; j++){
            if (b*ant<=j and dp[i][j]<dp[i-1][j-b*ant]+a*ant){
                dp[i][j]=dp[i-1][j-b*ant]+a*ant;
                if (ant<c) ant++;
            }else{
                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{
                        if (k<c) ant=k+1;
                        else ant=k;
                        break;
                    }
                }
            }
        }
    }cout<<dp[n][w];
    return 0;
}

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