Submission #881084

#	Time	Username	Problem	Language	Result	Execution time	Memory
881084		skywwla	Knapsack (NOI18_knapsack)	C++17	73 / 100	555 ms	196692 KiB

knapsack

#include <bits/stdc++.h>

using namespace std ;
using ll = long long ;

const int maxN = 5005 ;
const ll mod = 1e9 + 7 ;

int S , N, V[maxN], W[maxN], K[maxN] ;
ll dp[maxN][maxN] ;

ll solve(int i, int j) {
    if (i == N) return 0ll ;
    if (~dp[i][j]) return dp[i][j] ;
    ll ret = 0 ;
    for (ll c = 0 ; c <= K[i] && c * W[i] <= j ; c++) {
        ret = max(ret, solve(i + 1, j - c * W[i]) + c * V[i]) ;
    }
    dp[i][j] = ret ;
    return ret ;
}

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cin >> S >> N ;
    for (int i = 0 ; i < N ; i++) {
        cin >> V[i] >> W[i] >> K[i] ;
    }
    memset(*dp, -1, sizeof(dp)) ;
    cout << solve(0, S) ;
    return 0 ;
}

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