Submission #675427

#	Time	Username	Problem	Language	Result	Execution time	Memory
675427		Toxtaq	Knapsack (NOI18_knapsack)	C++17	37 / 100	132 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int S, n;
    cin >> S >> n;
    vector<pair<int, int> >items;
    items.push_back({0, 0});
    for(int i = 0;i < n;++i){
        int v, w, k;
        cin >> v >> w >> k;
        for(int j = 0;j < k;++j){
            items.push_back({w, v});
        }
    }
    n = items.size();
    int Max = 0;
    vector<vector<int> >dp(n, vector<int>(S + 1, -1e9));
    dp[0][0] = 0;
    for(int i = 1;i < n;++i){
        for(int j = S;j >= 0;--j){
            if(j - items[i].first >= 0)dp[i][j] = max(dp[i][j], dp[i - 1][j - items[i].first] + items[i].second);
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            Max = max(Max, dp[i][j]);
        }
    }
    cout << Max;
}

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