Submission #701640

#	Time	Username	Problem	Language	Result	Execution time	Memory
701640		Mohamed_Kachef06	Knapsack (NOI18_knapsack)	C++17	0 / 100	109 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> v, w , k;;
int dp[(int)1e5+2001][2001];
int knapsack(int i , int W){
    if (i==0) return 0 ;
    if (~dp[i][W]) return dp[i][W];
    int b =0 ;
    int a = knapsack(i-1 , W);
    if (W >= w[i]) b = knapsack(i-1  , W-w[i]) + v[i];
    return dp[i][W] = max(a , b);
}
signed main(){
    memset(dp , -1 , sizeof dp);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n , s ;
    cin >>  s >> n ;
    v.resize(n+1) , w.resize(n+1) , k.resize(n+1);
    for (int i = 1 ; i<=n ; i++){
        cin >> v[i] >> w[i] >> k[i];
        k[i] = min(s/w[i]  , k[i]);
    }
    for (int i = 1 ; i<=n ; i++){
        for (int j = 1 ; j<k[i] ; j++){
            w.push_back(w[i]); v.push_back(v[i]);
        }
    }
    n  = v.size();
    cout << knapsack(n , s);
}

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