제출 #720900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720900		lalig777	Knapsack (NOI18_knapsack)	C++14	29 / 100	2 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 ant=1;
            for (int k=ant; 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