Submission #1217826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217826		adityap2203	Knapsack (NOI18_knapsack)	C++20	73 / 100	170 ms	327680 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vector<int>>
#define forn(i,start,end) for(int i=start;i<end;i++)
#define pb push_back
#define fi first 
#define se second
#define all(x) x.begin(),x.end()
const int mod=1e9+7;
int main(){
    int s,n;
    cin>>s>>n;
    vvi a(n,vi(3));
    forn(i,0,n){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    vvi dp(n+1,vi(s+1));
    forn(i,1,n+1){
        forn(j,1,s+1){
             dp[i][j]=dp[i-1][j];
             for(int k=1;k<=a[i-1][2] && a[i-1][1]*k<=j;k++){
                    dp[i][j]=max(dp[i][j],a[i-1][0]*k +dp[i-1][j-k*a[i-1][1]]);
             }
        }
    }
    cout<<dp[n][s]<<endl;

}

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