Submission #1148125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148125		quangnamoiracvl_ralaidecu	Knapsack (NOI18_knapsack)	C++20	100 / 100	54 ms	2888 KiB

knapsack

/* Dirty code by Articulation_points */
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXS=2e3;
int n,m,v,w,t,dp[MAXS+5];
vector<pair<int,int>>wi[MAXS+5];
bool cmp(pair<int,int>x,pair<int,int>y){
    return x.first>y.first;
}
vector<int>val[MAXS+5];
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    cin>>m>>n;
    while(n--){
        cin>>v>>w>>t;
        wi[w].push_back({v,t});
    }
    for(int i=1;i<=m;++i)
        if(wi[i].size())
            sort(wi[i].begin(),wi[i].end(),cmp);
    for(int i=1;i<=m;++i){
        int j=0;
        bool check=false;
        for(pair<int,int>tmp:wi[i]){
            if(check)
                break;
            v=tmp.first;
            t=tmp.second;
            for(int k=j+1;k<=j+t;++k){
                if(k*i>m){
                    break;
                    check=true;
                }
                val[i].push_back(v);
            }
            j+=t;
        }
    }
    for(int i=1;i<=m;++i){
        for(int s=m;s>=0;--s){
            int sum=0;
            int cnt=0;
            for(int v:val[i]){
                sum+=v;
                cnt++;
                if(s>=cnt*i)
                    dp[s]=max(dp[s],dp[s-cnt*i]+sum);
            }
        }
    }
    cout<<dp[m]<<'\n';
}

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