Submission #1185300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185300		harryleee	Knapsack (NOI18_knapsack)	C++20	100 / 100	170 ms	250256 KiB

knapsack

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5;
const int maxw = 2000;
int W, n;
struct A {int w, v, num;}; A a[maxn];
vector<A> samew[maxw + 1], v;
bool cmp(A x, A y){return x.v > y.v;}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> W >> n;
    for (int i = 0; i < n; ++i){
        cin >> a[i].v >> a[i].w >> a[i].num;
        samew[a[i].w].push_back(a[i]);
    }
    for (int i = 1; i <= W; ++i){
        sort(samew[i].begin(), samew[i].end(), cmp);
    }
    for (int i = 1; i <= W; ++i){
        int target = W / i;
        for (int j = 0; j < samew[i].size() && target > 0; --target){
            v.push_back(samew[i][j]);
            if (--samew[i][j].num == 0) j++;
        }
    }
    vector<vector<int>> dp(v.size() + 1, vector<int> (W + 1, 0));
    for (int i = 1; i <= v.size(); ++i){
        for (int j = W; j >= 0; --j){
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i - 1].w) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1].w] + v[i - 1].v);
        }
    }
    cout << dp[v.size()][W];
}

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