Submission #483549

#	Time	Username	Problem	Language	Result	Execution time	Memory
483549		speedyArda	Knapsack (NOI18_knapsack)	C++14	49 / 100	112 ms	262148 KiB

knapsack

#include "bits/stdc++.h"

using namespace std; 

int main() 
{
    int s, n, va, we, k;
    cin >> s >> n;
    if(n == 1) // Subtask 1;
    {
        cin >> va >> we >> k;
        cout << min((s / we) * va, k * va);
    } else //Subtask 2 - 3;
    {
        vector<int> p;
        vector<int> w;
        
        for(int i = 0; i < n; i++) {
            cin >> va >> we >> k;
            while(k--) 
            {
                p.push_back(va);
                w.push_back(we);
            }
        }
        int k = p.size() + 1;
        long long dp[k][s + 1];
        for(int i = 0; i <= s; i++) 
            dp[0][i] = 0;
        for(int i = 1; i <= k - 1; i++) 
        {
            for(int a = 0; a <= s; a++) 
            {
                if(a - w[i - 1] >= 0)
                    dp[i][a] = max(dp[i - 1][a], dp[i - 1][a - w[i -1]] + p[i - 1]);
                else 
                    dp[i][a] = dp[i - 1][a]; 
            }
        }
        cout << dp[k - 1][s];
    }
}

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