Submission #970742

#	Time	Username	Problem	Language	Result	Execution time	Memory
970742		ttttttttttttth	Knapsack (NOI18_knapsack)	C++17	100 / 100	47 ms	4948 KiB

knapsack

// Author: Ivan Teo
// Created: Sat Apr 27 14:49:12 2024

#define TASKNAME "knapsack"
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=============================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}

void solve()
{
    int s, n;
    cin >> s >> n;
    vector<vector<ii>> a(s + 1);
    fore(i, 0, n - 1)
    {
        int v, w, k;
        cin >> v >> w >> k;
        a[w].pb(v, k);
    }
    vi f(s + 1);
    fore(w, 1, s)
    {
        sort(alll(a[w]), greater<ii>());
        auto cnt = s / w + 1;
        for (auto &[v, k] : a[w])
            while (cnt > 0 && k > 0)
            {
                k--;
                cnt--;
                for (int i = s; i >= w; i--) f[i] = max(f[i], f[i - w] + v);
            }
    }
    cout << *max_element(alll(f));
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("in", "r"))
        freopen("in", "r", stdin);
    if (fopen(TASKNAME ".inp", "r"))
        freopen(TASKNAME ".inp", "r", stdin),
                freopen(TASKNAME ".out", "w", stdout);
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen("in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
knapsack.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(TASKNAME ".inp", "r", stdin),
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |                 freopen(TASKNAME ".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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