Submission #719775

#	Time	Username	Problem	Language	Result	Execution time	Memory
719775		vjudge1	Knapsack (NOI18_knapsack)	C++14	100 / 100	69 ms	4620 KiB

knapsack

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

#define ll long long
#define ull unsigned long long
#define ed '\n'
#define pb push_back
#define ii pair<int,int>
#define o_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define fi first
#define se second
#define int long long

using namespace __gnu_pbds;
using namespace std;

void solve()
{
    int s, n;
    cin >> s >> n;

    vector<vector<ii>> g;
    g.resize(s + 10);

    for(int i = 1; i <= n; ++i) {
        int v, w, k;
        cin >> v >> w >> k;
        g[w].pb({v, k});
    }

    vector<ii> bag;
    for(int i = 1; i <= s; ++i) {
        sort(g[i].begin(), g[i].end(), greater<ii>());
        int need = s / i;
        for(auto [v, k]: g[i]) {
            for(int j = 1; j <= min(need, k); ++j) {
                bag.pb({v, i});
            }
            need -= k;
        }
    }

    vector<int> dp(s + 10);
    for(ii &x: bag) {
        for(int i = s; i >= x.se; --i) {
            dp[i] = max(dp[i], dp[i - x.se] + x.fi);
        }
    }
    cout << dp[s];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("cf.inp", "r"))
    {
        freopen("cf.inp", "r", stdin);
        //freopen("cf.inp", "w", stdout);
    }
    solve();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:36:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         for(auto [v, k]: g[i]) {
      |                  ^
knapsack.cpp: In function 'int main()':
knapsack.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen("cf.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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