Submission #1147670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147670		AlgorithmWarrior	Knapsack (NOI18_knapsack)	C++20	100 / 100	78 ms	1608 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

int const MAXN=1e5+5;
int const MAXS=2005;
int total_size,n;
struct food{
    int val,w,fr;
    bool operator<(food ot){
        if(w!=ot.w)
            return w<ot.w;
        return val>ot.val;
    }
}food[MAXN];

void read(){
    cin>>total_size>>n;
    int i;
    for(i=1;i<=n;++i){
        int val,w,fr;
        cin>>val>>w>>fr;
        food[i]={val,w,fr};
    }
    sort(food+1,food+n+1);
}

int add_val[MAXS];

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

int dp[MAXS];

int solve(){
    dp[0]=0;
    int i,j;
    for(i=1;i<=total_size;++i)
        dp[i]=-1;
    int id;
    for(id=1;id<=n;){
        int curr_w=food[id].w;
        int ind_add=0;
        while(food[id].w==curr_w){
            while(food[id].fr && ind_add<total_size){
                --food[id].fr;
                add_val[++ind_add]=food[id].val;
            }
            ++id;
        }
        for(i=total_size;i;--i){
            int val_added=0;
            for(j=1;j<=ind_add && i-j*curr_w>=0;++j){
                val_added+=add_val[j];
                maxself(dp[i],dp[i-j*curr_w]+val_added);
            }
        }
    }
    int maxim=0;
    for(i=1;i<=total_size;++i)
        maxself(maxim,dp[i]);
    return maxim;
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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