Submission #1127676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127676		heisenberg	Knapsack (NOI18_knapsack)	C++20	49 / 100	433 ms	327680 KiB

knapsack

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

long long knapsack(vector<long long> weights , vector<long long> & prices , long long W) {
    int N = weights.size() ;
    vector<long long> dp(W + 1,0) ;
    for(int i = N - 1 ; i >= 0 ; --i) {
        for(int cap = W ; cap >= weights[i] ; --cap) {
            dp[cap] = max(dp[cap],prices[i] + dp[cap - weights[i]]) ;
        }
    }
    return dp[W] ;
}

void run_case() {
    long long S , N ;
    cin >> S >> N ;
    if(N == 1) {
        long long value , weight , k = 0;
        cin >> value >> weight >> k ; 
        long long take = S / weight ;
        k = min(k,take) ;
        cout << value * k ;
        return ;
    }
    vector<long long> weights , prices ;
    for(int i = 0 ; i < N ; ++i) {
        long long value , weight , k = 0 ;
        cin >> value >> weight >> k ; 
        while(k--) {
            weights.push_back(weight) ;
            prices.push_back(value) ;
        }
    }
    cout << knapsack(weights,prices,S) ;
}

signed main() {
    run_case() ;
    return 0 ;
}

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