Submission #1225376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225376		sparsh0024	Knapsack (NOI18_knapsack)	C++20	17 / 100	1 ms	1096 KiB

knapsack

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int maxkilo,noitems;
    cin>>maxkilo>>noitems;
    vector<pair<int,pair<int,int>>> value(noitems);
    for(int i = 0;i<noitems;i++){
        cin>>value[i].second.first>>value[i].second.second>>value[i].first;
    }
    vector<vector<int>> dp(noitems+1,vector<int>(maxkilo+1,0));
    int maxi = 0;
   
    for(int i =1;i<noitems+1;i++){
         vector<int> howmany(maxkilo+1,0);
        for(int j = 1;j<maxkilo+1;j++){
            int take = 0;
            int nottake = dp[i-1][j];
            if(value[i-1].second.second <= j){
                take = value[i-1].second.first+dp[i-1][j-value[i-1].second.second];
                if(value[i].first >1){
                    int take2 = value[i-1].second.first+dp[i][j-value[i-1].second.second];
                    if(take2 >take){
                        howmany[j] = howmany[j-value[i-1].second.second]+1;
                        if(howmany[j] >= value[i].first){
                            take2  = 0;
                        }
                    }else{
                        howmany[j] = 1;
                    }
                    take = max(take,take2);
                } 
            }
            if(nottake >= take){
                howmany[j] = 0;
            }
            dp[i][j] = max(take,nottake);
            maxi  = max(maxi,dp[i][j]);
        }
    }
    cout<<maxi<<endl;
    return 0;
}

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