Submission #1178594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178594		Hezov	Knapsack (NOI18_knapsack)	C++20	100 / 100	85 ms	17336 KiB

knapsack

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct item{int val, cnt;};
vector<item> A[2002];
int dp[2001][2001];
// dp[i][j] - considerand greutati pana la i care e
// valoarea maxima obtinuta cu capacitatea j.
bool cmp(item a, item b)
{
    return a.val > b.val;
}
int main()
{
    int S, N;
    cin >> S >> N;
    for(int i = 1;i<=N;i++)
    {
        int v, w, k;
        cin >> v >> w >>  k;
        A[w].push_back({v,k});
    }
    for(int i = 1;i<=S;i++)
        if(!A[i].empty())
            sort(A[i].begin(),A[i].end(),cmp);

    for(int i = 1;i<=S;i++) // consideram greutatea i
    {
        // Avem un rucsac cu capacitatea G
        for(int G = 1;G<=S;G++)
        {
            int sumV = 0, taken = 0 ;
            dp[i][G] = dp[i-1][G];
            for(int j = 0; j < A[i].size();j++)
            {
                // Ne aflam intr-un item si nu stim cate sa luam din el.
                if(taken + 1 > G / i) break;
                for(int it = 1; it <= A[i][j].cnt;it++)
                {
                    if(taken + 1 > G / i) break;
                    taken++;
                    sumV += A[i][j].val;
                    dp[i][G] = max(dp[i][G], dp[i - 1][G - taken * i] + sumV);
                }
            }
        }

    }
    cout << dp[S][S] << '\n';
}

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