Submission #1284257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284257		dobri_oke	Knapsack (NOI18_knapsack)	C++20	100 / 100	38 ms	5476 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define int long long

const int N = 5e5+100;

void solve(){
    int s, n;
    cin >> s >> n;
    int a[n+1], b[n+1], c[n+1];
    vector < pair < int, int > > g[s+5];
    vector < pair < int, int > > v;
    for(int i=1;i<=n;i++){ 
        cin >> a[i] >> b[i] >> c[i];
        g[b[i]].pb({a[i], c[i]});
    }
    for(int i=1;i<=s;i++){ 
        sort(g[i].begin(), g[i].end());
        reverse(g[i].begin(), g[i].end());
    }
    for(int i=1;i<=s;i++){
        int mx=s/i, j=0;
        while(j<g[i].size() && mx>0){
            mx--;
            v.pb({g[i][j].F, i});
            g[i][j].S--;
            if(g[i][j].S==0) j++;
        }
    }
    int dp[s+1]{};
    for(int i=1;i<=s;i++) dp[i]=-1e18;
    for(auto [val, w] : v){
        for(int i=s-w;i>=0;i--){
            dp[i+w]=max(dp[i+w], dp[i]+val);
        }
    }
    int ans=0;
    for(int i=1;i<=s;i++) ans=max(ans, dp[i]);
    cout << ans;
}

signed main(){   
    ios_base::sync_with_stdio(0);   cin.tie(0);
    //freopen("promote.in","r",stdin);
    //freopen("promote.out","w",stdout);
    int tt=1;
   // cin >> tt;
    while(tt--){
        solve();
    }
}

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