Submission #1292596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292596		dex111222333444555	Knapsack (NOI18_knapsack)	C++20	100 / 100	53 ms	2796 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, MAXS = 2005;
const long long inf = 1e18 + 32;
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int lim, numVal;
long long dp[MAXS];

struct Node{
    int V, W, N;
    Node(int _V = 0, int _W = 0, int _N = 0):
        V(_V), W(_W), N(_N) {};
} val[MAXN];

void input(){
    cin >> lim >> numVal;
    for(int i = 1; i <= numVal; i++)
        cin >> val[i].V >> val[i].W >> val[i].N;
}

bool cmp(const Node &a, const Node &b){
    return (a.W < b.W || (a.W == b.W && a.V > b.V));
}

void solve(){
    sort(val + 1, val + 1 + numVal, cmp);
    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;
    int rep = 0;
    for(int i = 1; i <= numVal; i++){
        if (val[i].W != val[i - 1].W) rep = lim / val[i].W;
        for(int j = 0; j < min(rep, val[i].N); j++){
            for(int k = lim - val[i].W; k >= 0; k--) if (dp[k] > -inf) {
                maximize(dp[k + val[i].W], dp[k] + val[i].V);
            }
        }
        rep -= min(rep, val[i].N);
    }
    long long res = -inf;
    for(int i = 0; i <= lim; i++) maximize(res, dp[i]);
    cout << res << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solve();
}

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