제출 #1241383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241383		samarmahfooz	Knapsack (NOI18_knapsack)	C++20	37 / 100	149 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<vector<int>>> dp;
int s,n;
vector<int> value, weight, copies;

int find_ans(int level, int maxi, int can_take){
    if(level == n){
        return 0;
    }
    if(dp[level][maxi][can_take] != -1) return dp[level][maxi][can_take];
    int ans = 0;
    // take eleme // 
    if(can_take > 0 && maxi>=weight[level]) ans = max(ans, value[level] + find_ans(level, maxi-weight[level], can_take-1));
    // not take // 
    ans = max(ans, find_ans(level+1, maxi, copies[level+1]));

    return dp[level][maxi][can_take] = ans;
}

void solve(){
    cin>>s>>n;
    value.resize(n+1);
    copies.resize(n+1);
    weight.resize(n+1);
    int maxi = 0;
    for(int i=0;i<n;i++){
        cin>>value[i]>>weight[i]>>copies[i];
        maxi = max(maxi, copies[i]);
    }
    dp.assign(n, vector<vector<int>>(s+1, vector<int>(maxi+1, -1)));
    cout<<find_ans(0, s, copies[0])<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n_test = 1;
    // cin>>n_test;
    while(n_test--){
        solve();
    }
}

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