Submission #1082892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082892		timmyli3481	Knapsack (NOI18_knapsack)	C++14	73 / 100	89 ms	3708 KiB

knapsack

#include <bits/stdc++.h>
// #include "stdc++.h"
using namespace std;
struct grass{
    long long v,w,c;
};
long long dp[10000001];
grass a[10001];
int main(){
    int T,m;
    cin>>T>>m;
    for(int i=1;i<=m;i++){
        long long temp1,temp2,temp3;
        cin>>temp1>>temp2>>temp3;
        a[i]={temp1,temp2,temp3};
    }
    for(int i=1;i<=m;i++){
        for(int j=T;j>=a[i].w;j--){
            for(int z=0;z<=a[i].c;z++){

                if(j-a[i].w*z<0){
                    break;
                }
                dp[j]=max(dp[j],dp[j-a[i].w*z]+a[i].v*z);
                    
                
            }    
        }
    }
    cout<<dp[T];
}

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