제출 #1345308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1345308		vjudge1	Knapsack (NOI18_knapsack)	C++20	100 / 100	700 ms	428 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;

void solve(){
    ll n, s;
    cin>>s>>n;
    vector<ll> dp(s+1, 0);
    // dp[0]=1;
    for (int i=0; i<n; i++){
        ll v, w, k;
        cin>>v>>w>>k;
        k=min(k, s/w);
        ll x=1;
        while (k>0){
            ll say=min(k, x);
            ll V=say*v, W=say*w;
            for (int j=s; j>=W; j--){
                dp[j]=max(dp[j], dp[j-W]+V);
            }
            k-=say;
            x<<=1;
        }
    }
    ll ans=0;
    for (int i=0; i<=s; i++){
        ans=max(ans, dp[i]);
    }
    cout<<ans<<endl;
}

int main()
{
    ll T=1;
    // cin>>T;
    while (T--){
        solve();
    }

    return 0;
}

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