Submission #1147104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147104		sushanth123	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	324 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long s,n;
    cin >> s,n;
    vector<tuple<long long ,long long, long long>> in(n);
    long long total;
    total = 0;
    for(int i=0;i<n;i++){
        long long x,y,z;
        cin >> x >> y >> z;
        in[i] = {x,y,z};
        total += z;
    }
    long long dp[total+1][s+1] = {};
    for(int i=1;i<=s;i++){
        for(int j=1;j<=total;j++){
            if(get<1>(in[j-1]) <= i){
                dp[i][j] = max(dp[i][j-1],dp[i-get<1>(in[j-1])][j-1] + get<0>(in[j-1]));
            }
            else{
                dp[i][j] = dp[i][j-1];
            }
        }
    }
    cout << dp[total][s] << endl;
}

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