Submission #1083857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083857		tkvinhtruongquang	Knapsack (NOI18_knapsack)	C++14	73 / 100	1043 ms	2504 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int limit, type_num;
    cin >> limit >> type_num;

    vector<vector<pair<int, int>>> by_weight(limit + 1);

    for (int t = 0; t < type_num; t++) {
        int value, weight, amt;
        cin >> value >> weight >> amt;
        if (weight <= limit && amt > 0) {
            by_weight[weight].push_back({value, amt});
        }
    }

    vector<long long> best(limit + 1, INT32_MIN);
    best[0] = 0;

    for (int w = 1; w <= limit; w++) {
        if (!by_weight[w].empty()) {
            sort(by_weight[w].rbegin(), by_weight[w].rend());

            for (auto &item : by_weight[w]) {
                int value = item.first;
                int count = item.second;

                for (int j = limit; j >= w; j--) {
                    int copies = 0;
                    long long profit = 0;

                    while (copies < count && j >= (copies + 1) * w) {
                        copies++;
                        profit += value;
                        if (best[j - copies * w] != INT32_MIN) {
                            best[j] = max(best[j], best[j - copies * w] + profit);
                        }
                    }
                }
            }
        }
    }

    long long max_value = *max_element(best.begin(), best.end());
    cout << max_value << endl;

    return 0;
}

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