Submission #676846

#	Time	Username	Problem	Language	Result	Execution time	Memory
676846		Toxtaq	Knapsack (NOI18_knapsack)	C++17	49 / 100	375 ms	262144 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int S, N, sz = 0;
    cin >> S >> N;
    vector<int>values, weights;
    int V, W, K;
    if(N == 1){
        cin >> V >> W >> K;
        int num = S / W;
        cout << 1LL * min(num, K) * V;
        return 0;
    }
    for(int i = 0;i < N;++i){
        cin >> V >> W >> K;
        for(int j = 0;j < K;++j){
            values.push_back(V);
            weights.push_back(W);
        }
        sz += K;
    }

    vector<long long>dp(S + 1, -1e9);
    long long mx = 0;
    dp[0] = 0;

    for(int j = 0;j < sz;++j){
        for(int i = S;i >= 0;--i){
            if(i - weights[j] >= 0)dp[i] = max(dp[i - weights[j]] + 1LL * values[j], dp[i]);
//            cout << j << ", " << i << ": " << dp[i] << '\n';
            mx = max(mx, dp[i]);
        }
    }
    cout << mx;
}

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