제출 #1308429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308429		waigoon	Knapsack (NOI18_knapsack)	C++20	73 / 100	1097 ms	34884 KiB

knapsack

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
// #define f first
// #define s second
#define ve vector
#define emb emplace_back
#define em emplace
 
using namespace std;

const int inf = 1e18;
const int mod = 1e9 + 7;

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int s, n;
    cin >> s >> n;
    ve<priority_queue<pii>> pq(s+1);
    while (n--) {
        int v, w, k;
        cin >> v >> w >> k;
        k = min(k, s);
        pq[w].em(v, k);
    }
    ve<priority_queue<int>> a(s+1);
    for (int i = 1; i <= s; i++) {
        int rem = s;
        while (!pq[i].empty() && rem) {
            auto [val, cnt] = pq[i].top();
            pq[i].pop();
            if (cnt > rem) cnt = rem;
            rem -= cnt;
            while (cnt--) a[i].em(val);
        }
    }
    ve<int> dp(s+1, 0);
    for (int i = 1; i <= s; i++) {
        while (!a[i].empty()) {
            auto t = a[i].top();
            a[i].pop();
            for (int j = s - i; j >= 0; j--) dp[i+j] = max(dp[i+j], dp[j] + t);
        }
    }
    cout << dp[s];
}

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