Submission #1345422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345422		aaryyann	Knapsack (NOI18_knapsack)	C++20	37 / 100	0 ms	344 KiB

knapsack

#include<algorithm>
#include<vector>
#include<iostream>
#include<cmath>
#include<numeric>
using namespace std ;
using ll = int ;

void solve(){
    ll n , k;
    cin >> k >> n;

     vector<ll>dp(k+1 , 0);
    
    for(int i = 0 ; i < n ; i++){
        int price , w , cnt ;
        cin >> price >> w >> cnt ;
        

        // Binary Splitting Concept
        for(int j = 1 ; cnt > 0 ; j*= 2){
            int take = min(j , cnt);

            int new_w = w * take ;
            int new_price = price * take ;

            for(int p = k ; p >= new_w ; p--){
                dp[p] = max(dp[p] , dp[p - new_w] + new_price);
            }
            cnt-=take ;
        }
    }

    cout << dp[k] ;



}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll _t  = 1 ;
    // scin >> _t ;
    

    while(_t--){
        solve();
    }
}

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