Submission #1082896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082896		timmyli3481	Knapsack (NOI18_knapsack)	C++14	73 / 100	1031 ms	24912 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[100001];
int main(){
    int T,m;
    cin>>T>>m;
    int cnt=0;
    for(int i=1;i<=m;i++){
        long long v,w,c;
        cin>>v>>w>>c;
        int t=1;
        while(t<=c){
            a[++cnt].v=v*t;
            a[cnt].w=w*t;
            c-=t;
            t*=2;
        }
        if(c>0){
            a[++cnt].v=v*c;
            a[cnt].w=w*c;
        }
        
    }

    for(int i=1;i<=cnt;i++){
        for(int j=T;j>=a[i].w;j--){
           dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
        }
    }
    cout<<dp[T];
}

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