Submission #1189352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189352		fluke	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	2632 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long 
#define f first 
#define s second 
#define pii pair<int,int>
#define emb emplace_back
#define em emplace 
#define DB cout<<"\n";system("pause");
#define all(x) x.begin(),x.end()
#define sp <<" "<<
#define inf (int)(1e9)
#define INF (ll)(1e18)
#define mod (ll)(1e9 + 7)
using namespace std;

int main(){
ios::sync_with_stdio(false);cin.tie(0);
    int max_weight , item;
    cin>>max_weight>>item;

    ll weight[item] , value[item] , total[item];
    for(int i=0;i<item;i++) cin>>value[i] >> weight[i] >> total[i];
    
    ll dp[max_weight + 1];
    memset(dp,0,sizeof(dp));

    for(int i=0;i<item;i++){
        for(int j=max_weight ;j >= 0;j--){
            for(int k=1;k<=total[i] && j - weight[i] * k >= 0;  k++){
                dp[j] = max(dp[j] , dp[j - weight[i] * k] + value[i] * k);
            }            
        }

        // for(auto x : dp)cout<<x<<" ";
        // DB

    }

    cout<<dp[max_weight];

}

/*
 5 4
 1 3
 5 2
 4 2
 2 1
 5
 U 2 5
 A 2
 A 3
 U 1 4
 A 3
*/

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