Submission #720898

#	Time	Username	Problem	Language	Result	Execution time	Memory
720898		lalig777	Knapsack (NOI18_knapsack)	C++14	73 / 100	191 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;
        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: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27