Submission #794198

#	Time	Username	Problem	Language	Result	Execution time	Memory
794198		Kalpit1810	Knapsack (NOI18_knapsack)	C++17	100 / 100	121 ms	34248 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long n, s;
    cin >> s >> n;

    map<long long, vector<pair<long long, long long>>> items;

    for (long long i = 0; i < n; i++)
    {
        long long a, b, c;
        cin >> a >> b >> c;
        items[b].push_back({a, c});
    }

    vector<vector<long long>> dp(items.size()+1, vector<long long>(s + 1, INT64_MIN));
    dp[0][0]=0;
    long long at = 1;

    for (auto p : items)
    {
        long long w =p.first;
        vector<pair<long long,long long>> item = p.second;
        sort(item.begin(), item.end(), greater<pair<int, int>>());
        for (int i = 0; i < s + 1; i++)
        {
            dp[at][i] = dp[at - 1][i];
            long long copies = 0;
            long long type = 0;
            long long value = 0;
            long long curr = 0;

            while ((copies + 1) * w <= i && type < item.size())
            {
                value += item[type].first;
                copies++;
                curr++;

                if(dp[at-1][i-copies*w] != INT64_MIN)
                {
                    dp[at][i] = max(dp[at][i],dp[at-1][i-copies*w]+value);
                }

                if (curr==item[type].second){
                    curr=0;
                    type++;
                }
            }
        }
        at++;
    }

    cout << *max_element(dp.back().begin(), dp.back().end());
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:36:50: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             while ((copies + 1) * w <= i && type < item.size())
      |                                             ~~~~~^~~~~~~~~~~~~

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