제출 #1128453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128453		mtshasta	Knapsack (NOI18_knapsack)	C++20	100 / 100	86 ms	34376 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 1e5;
const int MAXS = 2e3;

ll dp[MAXN + 1][MAXS + 1];

void solve() {
    map<int, vector<pii>> by_weights;
    int S, N;
    cin >> S >> N;
    vector<int> V(N), W(N), K(N);
    for (int i = 0; i < N; ++i) {
        cin >> V[i] >> W[i] >> K[i];
        by_weights[W[i]].push_back(make_pair(V[i], K[i]));
    }
    int id = 1;
    for (auto &[k, v] : by_weights) {
        sort(v.begin(), v.end(),
             [](pii &a, pii &b) { return a.first > b.first; });
        for (int i = 1; i <= S; ++i) {
            dp[id][i] = dp[id - 1][i];
            int cnt = 1, sz = 0, curr = 0;
            ll tot = 0;
            while (i >= cnt * k && sz < v.size()) {
                tot += v[sz].first;
                dp[id][i] = max(dp[id][i], dp[id - 1][i - cnt * k] + tot);
                ++cnt;

                ++curr;
                if (curr == v[sz].second) {
                    curr = 0;
                    ++sz;
                }
            }
        }
        ++id;
    }
    cout << *max_element(dp[by_weights.size()], dp[by_weights.size()] + S + 1)
         << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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