제출 #1301952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301952		vaderspader	Knapsack (NOI18_knapsack)	C++20	12 / 100	1 ms	576 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> matrix;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define down(i, b, a) for(ll i = b - 1; i >= a; i--)

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll s, n;
    cin >> s >> n;

    vi v(0);
    vi w(0);

    rep(i, 0, n){
        ll V, W, K;
        cin >> V >> W >> K;

        ll c = 1;

        while(K > c){
            v.push_back(c * V);
            w.push_back(c * W);
            K -= c;
            c <<= 1;
        }
        v.push_back(K * V);
        w.push_back(K * W);
    }

    n = v.size();

    vi dp(s + 1, 0);

    set<ll> pos;
    pos.insert(0);

    rep(i, 0, n){
        vi temp(0);
        for(ll c : pos){
            if(c + w[i] > s) continue;
            dp[c + w[i]] = max(dp[c + w[i]], dp[c] + v[i]);
            temp.push_back(c + w[i]);
        }
        for(ll c : temp){
            pos.insert(c);
        }
    }

    ll best = 0;
    rep(i, 0, s + 1) best = max(best, dp[i]);
    
    cout << best << endl;
}

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