Submission #881093

#	Time	Username	Problem	Language	Result	Execution time	Memory
881093		skywwla	Knapsack (NOI18_knapsack)	C++17	49 / 100	1094 ms	10388 KiB

knapsack

#include <bits/stdc++.h>

using namespace std ;
using ll = long long ;

const int maxN = 5005, M = 1e5 + 5 ;
const ll mod = 1e9 + 7 ;

int S , N, V[M], W[M], K[M] ;
vector<map<int,ll>> dp(2001) ;

ll solve(int i, int j) {
    if (i == N) return 0ll ;
    if (dp[j].count(i)) return dp[j][i] ;
    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[j][i] = 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] ;
    }
    cout << solve(0, S) ;
    return 0 ;
}

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