Submission #1313951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313951		Agageldi	Knapsack (NOI18_knapsack)	C++20	73 / 100	155 ms	327680 KiB

knapsack

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

#define int long long
#define N 500005

int tc = 1, n, a[N], S, v[N], w[N], k[N], dp[100001][2001], mx, pos[N];

int32_t main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> S >> n;
    for(int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i] >> k[i];
    }
    pos[0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= S; j++) {
            dp[i][j] = dp[i - 1][j];
            int sum = 0, cost = 0, l = k[i];
            while(l--) {
                sum += w[i];
                cost += v[i];
                if(sum > j) break;
                if(pos[j - sum]){
                    dp[i][j] = max(dp[i][j],dp[i - 1][j - sum] + cost);
                    pos[j] = 1;
                }
            }
        }
    }
    for(int i =0;i <= S; i++) {
        mx = max(mx,dp[n][i]);
    }
    cout << mx << '\n';
    return 0;
}

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