Submission #1336586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1336586		ghassanhasan	Knapsack (NOI18_knapsack)	C++20	100 / 100	37 ms	1808 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(v) v.begin(), v.end()

void doing() {
    int s, n; cin >> s >> n;
    vector<vector<pair<int, int>>> v(s + 1);
    for(int i = 0; i < n; i++) {
        int val, w, k; cin >> val >> w >> k;
        v[w].emplace_back(val, k);
    }
    for(int i = 1; i <= s; i++) sort(all(v[i]), greater());
    vector a(s + 1, vector<int>());
    for(int i = 1; i <= s; i++){
        int cur = s;
        for(int j = 0; j < v[i].size(); j++){
            while(cur >= i && v[i][j].second) {
                a[i].push_back(v[i][j].first);
                cur -= i;
                v[i][j].second--;
            }
        }
    }
    vector<ll> dp(s + 1);
    for(int i = 1; i <= s; i++){
        for(auto it: a[i])
            for(int j = s - i; j >= 0; j--){
                dp[j + i] = max(dp[j + i], dp[j] + it);
            }
    }
    cout << *max_element(all(dp)) << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
{
#ifdef GH
    freopen("IN.txt", "r", stdin);
    cout << string(60, '*') << endl;
#else
    if (const string file = ""; !file.empty()) {
        freopen((file + ".in").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }
#endif
}
    int tc = 1;
    // cin >> tc;
    while (tc--)
        doing();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen((file + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen((file + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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