Submission #1065981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065981		KALARRY	Knapsack (NOI18_knapsack)	C++14	100 / 100	46 ms	3676 KiB

knapsack

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,S,dp[2005]; //max val with space i
vector<pair<int,int>> items[2005];

int main()
{
    scanf("%d%d",&S,&N);
    for(int v,w,k,i = 1 ; i <= N ; i++)
    {
        scanf("%d%d%d",&v,&w,&k);
        items[w].push_back({v,k});
    }
    for(int i = 1 ; i <= S ; i++)
    {
        sort(items[i].begin(),items[i].end(),greater<pair<int,int>>());
        int space_taking = 0;
        for(auto e : items[i])
        {
            int v = e.first;
            int w = i;
            int k = e.second;
            for(int x = 1 ; space_taking <= S && x <= k ; x++)
            {
                space_taking += w;
                if(space_taking <= S)
                {
                    for(int j = S ; j >= w ; j--)
                        dp[j] = max(dp[j],dp[j-w] + v);
                }
            }
        }
    }
    printf("%d\n",dp[S]);
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d%d",&S,&N);
      |     ~~~~~^~~~~~~~~~~~~~
knapsack.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d%d%d",&v,&w,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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