Submission #1194312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194312		nagorn_ph	Knapsack (NOI18_knapsack)	C++20	100 / 100	39 ms	3268 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};

int32_t main(){
    iShowSpeed;
    int s, n; cin >> s >> n;
    priority_queue <pii> pq[s + 1];
    for (int i = 0; i < n; i++) {
        int v, w, s; cin >> v >> w >> s;
        pq[w].emplace(v, s);
    }
    vector <pii> a;
    for (int i = 1; i <= s; i++) {
        int cnt = (s + i - 1) / i;
        while (!pq[i].empty()) {
            auto [v, s] = pq[i].top(); pq[i].pop();
            int ss = s;
            while (cnt > 0 && ss > 0) a.emb(v, i), ss--, cnt--;
            if (cnt == 0) break;
        }
    }
    vector <int> dp(s + 1);
    int ans = 0;
    for (auto [v, w] : a) {
        for (int i = s; i >= w; i--) {
            dp[i] = max(dp[i], dp[i - w] + v);
            ans = max(ans, dp[i]);
        }
    }
    cout << ans;
}

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