제출 #1345575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1345575		aaryyann	Knapsack (NOI18_knapsack)	C++20	100 / 100	676 ms	452 KiB

knapsack

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

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

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

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

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

            for(ll 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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27