제출 #1242544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242544		menkh	Knapsack (NOI18_knapsack)	C++17	100 / 100	58 ms	34376 KiB

knapsack

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

#define int long long
// #define ll long long

#define MAX_N 100005
#define MAX_W 2005
int dp[MAX_N][MAX_W];
int S, n;

void solve() {
    cin >> S >> n; 
    map<int, vector<pair<int, int>>> items; 
    for (int i = 0; i < n; i++) {
        int value, weight, num; 
        cin >> value >> weight >> num;
        items[weight].push_back({value, num});
    }

    dp[0][0] = 0;
    int i = 1;

    for (auto &it : items) {
        sort(it.second.begin(), it.second.end(), greater<pair<int ,int>>());
        for (int w = 0; w <= S; w++) {
            dp[i][w] = dp[i - 1][w];
            int at = 0, k = 0, cur_k = 0, profit = 0;

            while ((k + 1) * it.first <= w && at < it.second.size()) {
                k++;
                profit += it.second[at].first;
                dp[i][w] = max(dp[i][w], dp[i - 1][w - k * it.first] + profit);

                cur_k++; 
                if (cur_k == it.second[at].second) {
                    cur_k = 0; 
                    at++;
                }
            }
        }
        i++;
    }

    int answer = 0;
    for (int w = 0; w <= S; w++) answer = max(answer, dp[items.size()][w]);
    cout << answer << '\n'; 
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // int t; cin >> t; 
    while (t--) solve();
}

// 1 MB = 1000000 bytes
// 1 int = 4 bytes
// memory consumption: (sizeof(...)_int * 4) / 1000000

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