제출 #688657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
688657		tcmmichaelb139	Knapsack (NOI18_knapsack)	C++17	73 / 100	1062 ms	2644 KiB

knapsack

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

struct node {
    long long v, w, k;
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    long long s, n;
    cin >> s >> n;
    vector<node> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].v >> v[i].w >> v[i].k;

    sort(begin(v), end(v), [](node a, node b) {
        if (a.v == b.v) return a.w < b.w;
        return a.v > b.v;
    });

    long long dp[s + 1];
    memset(dp, 0, sizeof dp);

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        for (long long j = s; j >= 0; j--) {
            for (long long a = min(v[i].k, (s - j) / v[i].w); a >= max(min(v[i].k, (s - j) / v[i].w) - 10, 0ll); a--) {
                dp[j + v[i].w * a] = max(dp[j + v[i].w * a], dp[j] + v[i].v * a);
                ans = max(ans, dp[j + v[i].w * a]);
            }
            for (long long a = 0; a <= min(10ll, min(v[i].k, (s - j) / v[i].w)); a++) {
                dp[j + v[i].w * a] = max(dp[j + v[i].w * a], dp[j] + v[i].v * a);
                ans = max(ans, dp[j + v[i].w * a]);
            }
        }
    }

    cout << ans << '\n';
}

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