Submission #689414

#	Time	Username	Problem	Language	Result	Execution time	Memory
689414		tcmmichaelb139	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	340 KiB

knapsack

#include "bits/stdc++.h"
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int s, n;
    cin >> s >> n;
    vector<vector<pair<long long, long long>>> v(s + 1);
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[b].push_back({a, c});
    }

    long long dp[s + 1];
    for (int i = 0; i <= s; i++)
        dp[i] = -1;
    dp[0] = 0;

    for (int i = 1; i <= s; i++) {
        sort(rbegin(v[i]), rend(v[i]));
        if (v[i].size() == 0) continue;

        for (int j = s; j >= 0; j--) {
            if (dp[j] == -1) continue;

            long long cur = j + i;
            long long num = 0;
            long long val = 0;
            while (cur <= s) {
                if (v[i][num].second == 0) num++;
                if (num == v[i].size()) break;

                val += v[i][num].first;
                v[i][num].second--;

                dp[cur] = max(dp[cur], dp[j] + val);

                cur += i;
            }
        }
    }

    cout << *max_element(dp, dp + s + 1) << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:34:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                 if (num == v[i].size()) break;
      |                     ~~~~^~~~~~~~~~~~~~

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