Submission #1203821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203821		Iskachun	Knapsack (NOI18_knapsack)	C++20	100 / 100	94 ms	34372 KiB

knapsack

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
void solve () {
    ll s, n; cin >> s >> n;
    map<ll, vector<pair<ll,ll>>> mp;
    for (ll i = 0; i < n; i++) {
        ll a, b, c; cin >> a >> b >> c;
        if (b <= s and c > 0) {
            mp[b].push_back({a, c});
        }
    }
    vector<vector<ll>> dp(mp.size() + 1, vector<ll> (s + 1, -1e18));
    dp[0][0] = 0;
    ll pos = 1;
    for (auto [x, y] : mp) {
        sort(y.begin(), y.end(), greater<pair<ll,ll>>());
        for (ll i = 0; i <= s; i++) {
            dp[pos][i] = dp[pos - 1][i];
            ll cnt = 0, j = 0, curr = 0, profit = 0;
            while ((cnt + 1) * x <= i and j < y.size()) {
                cnt++;
                profit += y[j].first;
                if (dp[pos - 1][i - cnt * x] != -1e18) {
                    dp[pos][i] = max(dp[pos][i], dp[pos - 1][i - cnt * x] + profit);
                }
                curr++;
                if (curr == y[j].second) {
                    curr = 0;
                    j++;
                }
            }
        }
        pos++;
    }
    cout << *max_element(dp.back().begin(), dp.back().end());
}
int main() {
    //freopen("filename.in", "r", stdin), freopen("filename.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; //cin >> t;
    while (t--) solve();
}

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