Submission #1342502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342502		darkshadowz	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	460 KiB

knapsack

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define int long long
using namespace std;

int dp[2069];

signed main(){

    cin.tie(0); ios::sync_with_stdio(0);
    int w, n; cin >> w >> n;
    for(int i=1; i<=n; i++){
        int v, a, k; cin >> v >> a >> k;
        for(int j=1; k>0; j<<=1){
            int W = a*min(j,k), V = v*min(j,k);
            for(int x=w; x-W>=0; x--)
                dp[x] = max(dp[x], dp[x-W]+V);
            k -= j;
        }
    }
    cout << dp[w];

    return 0;
}

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