Submission #1152248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152248		sodbayr	Knapsack (NOI18_knapsack)	C++20	100 / 100	55 ms	3340 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ss second
#define ff first
#define pb push_back
const ll mxs=2e3;
ll n,m,v,w,t,dp[mxs+5];
vector<pair<ll,ll>>wi[mxs+5];
bool cmp(pair<ll,ll>x,pair<ll,ll>y){return x.ff>y.ff;}
vector<ll>val[mxs+5];
int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin>>m>>n;
    while(n--) {
		cin>>v>>w>>t;
		wi[w].pb({v,t});
	}
    for(ll i=1;i<=m;i++) 
		if(wi[i].size()) sort(wi[i].begin(),wi[i].end(),cmp);
    for(ll i=1;i<=m;i++) {
        ll j=0;
		bool ck=0;
        for(auto tmp:wi[i]){
            if(ck) break;
            v=tmp.ff;t=tmp.ss;
            for(ll k=j+1; k<=j+t; k++) {
                if(k*i>m) {break;ck=1;}
                val[i].pb(v);
            }
            j+=t;
        }
    }
    for(ll i=1;i<=m;i++) {
        for(ll s=m;s>=0;s--) {
            ll sum=0,cnt=0;
            for(ll 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