Submission #1354818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354818		askelad	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	2624 KiB

knapsack

#include<bits/stdc++.h>

#define ll  long long

using namespace std;





void solve(int test){
    int s,n;
    cin>>s>>n;

    vector<pair<ll,int>>vec[s+1];

    ll w,v,k;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>k;
        vec[w].push_back({v,k});
    }

    ll dp[s+1]={};
    for(int i=1;i<=s;i++){
        sort(vec[i].begin(),vec[i].end());
        reverse(vec[i].begin(),vec[i].end());
        int cur=(s/i)+1;
        for(auto [v,k]:vec[i]){
            if(cur==0)break;
            int aux=min(cur,k);
            while(aux--){
                for(int u=s;u>=i;u--)dp[u]=max(dp[u],dp[u-i]+v);
            }
            cur-=aux;
        }
    }

    ll ans=0;
    for(auto x:dp)ans=max(ans,x);
    cout<<ans;

}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;

    // cin>>t;
    for(int i=1;i<=t;i++)
        solve(i);
}

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