Submission #1135423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135423		yeroc	Knapsack (NOI18_knapsack)	C++17	100 / 100	68 ms	33096 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> intpair;
typedef pair<ll, ll> llpair;
// const int MOD = 1e9 + 7;

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int maxWeight, typeCnt; cin >> maxWeight >> typeCnt;
    
    map<int, vector<intpair>> byWeight;
    for (int t = 0; t < typeCnt; t++) {
        int value, weight, amt; cin >> value >> weight >> amt;
        if (weight <= maxWeight && amt > 0) {
            byWeight[weight].push_back({value, amt});
        }
    }
    
    vector<vector<ll>> dp(byWeight.size() + 1, vector<ll>(maxWeight + 1, INT32_MIN));
    
    dp[0][0] = 0;
    int at = 1;
    for (auto &[w, items] : byWeight) {
        sort(items.begin(), items.end(), greater<intpair>());
        for (int i = 0; i <= maxWeight; i++) {
            dp[at][i] = dp[at - 1][i];
            int copies = 0;
            int typeAt = 0;
            int currUsed = 0;
            ll profit = 0;
            
            while ((copies + 1) * w <= i && typeAt < items.size()) {
                copies++;
                profit += items[typeAt].first;
                if (dp[at - 1][i - copies * w] != INT32_MIN) {
                    dp[at][i] = max(dp[at][i], dp[at - 1][i - copies * w] + profit);
                }

                currUsed++;
                if (currUsed == items[typeAt].second) {
                    currUsed = 0;
                    typeAt++;
                }
            }
        }
        at++;
    }
    
    cout << *max_element(dp.back().begin(), dp.back().end()) << endl;
}

int main() {
    solve();
    return 0;
}

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