제출 #1101698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1101698		TudorMa	Knapsack (NOI18_knapsack)	C++14	100 / 100	45 ms	7628 KiB

knapsack

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

#define fi first
#define sc second
#define int long long

using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 5, W = 2005;

struct item {
    int s, w, k;
};

int n, w, dp[W];
item v[N];
vector<pii> weights[W];

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(0);

    cin >> w >> n;
    for(int i=1; i<=n; i++) {
        cin >> v[i].s >> v[i].w >> v[i].k;
        weights[v[i].w].push_back({v[i].s, v[i].k});
    }

    for(int i=1; i<W; i++)
        dp[i] = -1;
    for(int i=1; i<=w; i++) {
        if(weights[i].empty())
            continue;

        sort(weights[i].begin(), weights[i].end());

        int cnt = 0;
        while(cnt < w / i && weights[i].size()) {
            cnt++;
            pii x = weights[i].back();
            for(int j=w; j>=i; j--)
                if(dp[j-i] > -1)
                    dp[j] = max(dp[j], dp[j-i] + x.fi);

            x.sc--;
            if(x.sc)
                weights[i][weights[i].size()-1] = x;
            else weights[i].pop_back();
        }
    }

    int ans = 0;
    for(int i=0; i<=w; i++)
        ans = max(ans, dp[i]);

    cout << ans;
    return 0;
}

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