Submission #1302034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302034		vaderspader	Knapsack (NOI18_knapsack)	C++20	100 / 100	103 ms	40316 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 n, s;
    cin >> s >> n;

    matrix pos(s + 1, vi(0));

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

        ll c = 1;

        while(K > c){
            if(W * c <= s){
                pos[W * c].push_back(V * c);
            }

            K -= c;
            c <<= 1;
        }

        if(W * K <= s){
            pos[W * K].push_back(V * K);
        }
    }

    rep(i, 0, s + 1){
        sort(pos[i].begin(), pos[i].end(), greater<ll>());
    }

    matrix next(s + 1, vi(s + 1, 0));

    vi dp(s + 1, 0);

    rep(i, 0, s + 1){
        ll ind = -1;
        ll best = 0;

        rep(j, 0, i){
            if(pos[i - j].size() == next[j][i - j]) continue;

            ll curr = pos[i - j][next[j][i - j]];
            if(curr + dp[j] > best){
                ind = j;
                best = curr + dp[j];
            }
        }

        if(ind != -1){
            dp[i] = best;
            next[i] = next[ind];
            next[i][i - ind]++;
        }
    }

    ll m = 0;
    rep(i, 0, s + 1) m = max(dp[i], m);

    cout << m << endl;
}

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