Submission #789070

#	Time	Username	Problem	Language	Result	Execution time	Memory
789070		olisoe	Knapsack (NOI18_knapsack)	C++11	100 / 100	68 ms	35148 KiB

knapsack

#include "iostream"
#include "vector"
#include "algorithm"
#include "queue"
#include "set"
#include "unordered_set"
#include "stack"
#include "map"
#include "limits.h"
#include "cstdio"
#include "math.h"
#include <numeric>
using namespace std;



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int limit, n;
    cin>>limit>>n;
    map<int, vector<pair<int,int>>> weight;
    for(int i = 0; i<n; i++)
    {
        int value,wei,amt;
        cin>>value>>wei>>amt;
        if(wei<=limit&&amt>0)
            weight[wei].push_back(make_pair(value,amt));
    }
    vector<vector<long long>> dp(weight.size()+1,vector<long long>(limit+1,INT32_MIN));
    dp[0][0]=0;
    int at = 1;
    for(auto &[w,items]:weight)
    {
        sort(items.begin(),items.end(),greater<pair<int,int>>());
        for(int i = 0; i<=limit; i++)
        {
            dp[at][i]=dp[at-1][i];
            int copies = 0;
            int typeat = 0;
            int used = 0;
            long long profit = 0;
            while((copies+1)*w<=i&&typeat<items.size())
            {
                copies++;
                profit+=items[typeat].first;
                if(dp[at-1][i-copies*w]!=INT_MAX)
                {
                    dp[at][i]= max(dp[at][i],dp[at-1][i-copies*w]+profit);
                }
                used++;
                if(used == items[typeat].second)
                {
                    used = 0;
                    typeat++;
                }
            }
        }
        at++;
    }
    cout<<*max_element(dp.back().begin(),dp.back().end());
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for(auto &[w,items]:weight)
      |               ^
knapsack.cpp:43:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             while((copies+1)*w<=i&&typeat<items.size())
      |                                    ~~~~~~^~~~~~~~~~~~~

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