Submission #1363088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363088		deepak23232	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	2764 KiB

knapsack

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define int long long


void solve() {
    int s,n;
    cin>>s>>n;
    vector<int> prices(n);
    vector<int> size(n);
    vector<int> copies(n);

    for(int i=0; i<n; i++){
        cin>>prices[i];
        cin>>size[i];
        cin>>copies[i];
    }

    vector<int> dp(s+1,INT_MIN);
    dp[0] = 0;

    int maxi = -1;

    for(int i=0; i<n; i++){
        int cnt = 1;
        while(cnt<=copies[i] && cnt*size[i]<=s){
            for(int j=s; j>=size[i]; j--){
                dp[j] = max(dp[j],prices[i]+dp[j-size[i]]);
                maxi = max(maxi,dp[j]);
            }
            cnt++;
        }
    }
    cout<<maxi<<endl;

    
}

signed main() {
    int t=1;
    // cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}

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