제출 #917027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917027		blessyou	Knapsack (NOI18_knapsack)	C++17	100 / 100	269 ms	4976 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int INF = 1e15, MOD = 1e9 + 7;

mt19937_64 rnd(441225); // ddly

int binpow(int x, int a) {
    int ret = 1;
    while (a > 0) {
        if (a & 1) {
            ret *= x;
            ret %= MOD;
            a--;
        } else {
            x *= x;
            x %= MOD;
            a >>= 1;
        }
    }
    return ret;
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int s, n;
    cin >> s >> n;
    vector<int> v(n), w(n), k(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i] >> w[i] >> k[i];
    }
    vector<int> dp(s + 1);
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        vector<int> ndp = dp;
        while (cnt > 0 && k[i]-- > 0) {
            cnt = 0;
            for (int j = w[i]; j <= s; j++) {
                if (dp[j - w[i]] + v[i] > dp[j]) {
                    cnt++;
                    ndp[j] = dp[j - w[i]] + v[i];
                }
            }
            dp = ndp;
        }
    }
    cout << dp[s];
}

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