Submission #1307942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307942		Alexe1900	Knapsack (NOI18_knapsack)	C++20	29 / 100	6 ms	588 KiB

knapsack

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

#define int long long

signed main() {
    int n, c;
    cin >> c >> n;

    vector<int> weight(n), value(n), amount(n);
    for (int i = 0; i < n; i++) cin >> value[i] >> weight[i] >> amount[i];

    vector<int> dp(c+1, -1); dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int rem = 0; rem < weight[i]; rem++) {
            deque<pair<int, int>> q;
            if (dp[rem] != -1) q.push_back({dp[rem], rem});

            for (int p = rem + weight[i]; p <= c; p += weight[i]) {
                while (!q.empty() and q.front().second < p - weight[i] * amount[i]) q.pop_front();

                while (!q.empty() and q.back().first + value[i] <= dp[p]) q.pop_back();
                if (dp[p] != -1) q.push_back({dp[p], p});
                
                if (!q.empty()) dp[p] = max(dp[p], q.front().first + (p - q.front().second) / weight[i] * value[i]);
            }
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

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