제출 #1292586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292586		dex111222333444555	Knapsack (NOI18_knapsack)	C++20	12 / 100	2 ms	2624 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, MAXS = 2005;
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(){
    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--){
                maximize(dp[k + val[i].W], dp[k] + val[i].V);
            }
        }
        rep -= min(rep, val[i].N);
    }
    long long res = -1e18;
    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: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27