제출 #767688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767688		vjudge1	Knapsack (NOI18_knapsack)	C++17	0 / 100	98 ms	262144 KiB

knapsack

/* {وَقُلْ رَبِّ زِدْنِي عِلْمًاً} */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mem(ARR, XX) memset(ARR,XX,sizeof ARR)
#define TY cin.tie(0), cout.tie(0),cin.sync_with_stdio(0), cout.sync_with_stdio(0);
int const N = 1e6 + 5;
ll dp[100][N];
int n,w;
struct item{ll w,v,k;};
item it[N];
ll slv(int i,ll W) {
    if (i == n || !W)return 0;
    ll &ret = dp[i][W];
    if (~ret)return ret;
    for (int j = 0; j <= it[i].k; ++j)
        if (W - it[i].w * j >= 0)
            ret = max(ret, slv(i + 1, W - it[i].w * j) + it[i].v * j);
    return ret;
}
void jo() {
    mem(dp, -1);
    cin >> w >> n;
    for (int i = 0; i < n; ++i)
        cin >> it[i].v >> it[i].w >> it[i].k;
    cout << slv(0, w);
}
int main() {
    TY
    jo();
}

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