제출 #998060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998060		coolboy19521	Knapsack (NOI18_knapsack)	C++17	0 / 100	11 ms	13008 KiB

knapsack

#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"

#define int long long

using namespace std;

const int sz = 1e5 + 5;
const int sm = 2e3 + 3;

int dp[sm][sz];
bool v[sz];

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, s;

    cin >> s >> n;

    vector <int> a, b;
    a = {0}, b = {0};

    for (int i = 1; i <= n; i ++) {
        int v, w, k;
        cin >> v >> w >> k;

        for (int j = 0; (1 << j) < k; j ++) {
            a.push_back((1 << j) * v);
            b.push_back((1 << j) * w);
            k -= (1 << j);
        }

        if (0 < k) {
            a.push_back(k * v);
            b.push_back(k * w);
        }
    }

    int m = a.size() - 1;

    v[0] = true;

    for (int i = 1; i <= m; i ++) {
        for (int j = s; 0 <= j - b[i]; j --) {
            if (v[j - b[i]]) {
                dp[j][i] = dp[j - b[i]][i - 1] + a[i];
                v[j] = true;
            }

            dp[j][i] = max(dp[j][i], dp[j][i - 1]);
        }
    }

    int mx = 0;

    for (int i = 0; i <= s; i ++) {
        mx = max(mx, dp[i][m]);
    }

    cout << mx << '\n';
}

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