Submission #1301987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301987		vaderspader	Knapsack (NOI18_knapsack)	C++20	73 / 100	1002 ms	2840 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--)

struct info{
    ll v, w, k;

    info(){}
};

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

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

    vector<info> a(n);

    rep(i, 0, n){
        cin >> a[i].v >> a[i].w >> a[i].k;
    }

    vi dp(s + 1, 0);
    vi best(s + 1, 0);

    rep(i, 0, n){
        rep(mod, 0, a[i].w){
            deque<ll> now;

            rep(curr, 0, ((s + 1)) / a[i].w + 10000){
                if(mod + curr * a[i].w > s) break;

                while(!now.empty() && curr - now.front() > a[i].k){
                    now.pop_front();
                }

                while(!now.empty() && dp[now.back() * a[i].w + mod] + (curr - now.back()) * a[i].v <= dp[mod + curr * a[i].w]){
                    now.pop_back();
                }

                now.push_back(curr);

                ll f = now.front();

                best[mod + curr * a[i].w] = (curr - f) * a[i].v + dp[f * a[i].w + mod];
            }
        }

        rep(j, 0, s + 1){
            dp[j] = max(dp[j], best[j]);
        }
    }

    cout << dp.back() << endl;
}

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