Submission #1005640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005640		kvintsekstakord	Knapsack (NOI18_knapsack)	C++17	100 / 100	127 ms	255612 KiB

knapsack

#include <bits/stdc++.h>
#define int int64_t
using namespace std;

int S, N;

vector<vector<pair<int, int> > > vk(2010, vector<pair<int, int>>());

vector<int> w={0};
vector<int> v={0};

int dp[2010][16000];

int32_t main()
{

    cin >> S >> N;
    for(int i = 1; i <= N; i++){
        int vi, wi, ki; cin >> vi >> wi >> ki;
        vk[wi].push_back({vi, ki});
    }
    for(int i = 1; i <= 2000; i++){
        sort(vk[i].begin(), vk[i].end(), greater<pair<int, int> >());
        int sum = 0;
        for(int j = 0; j < vk[i].size(); j++){
            int vi = vk[i][j].first;
            int k = vk[i][j].second;

            int e;
            if(sum+k<=(2000/i)){
                e=k;
                sum+=k;
            }else{
                e = (2000/i)-sum;
                sum = (2000)/i;
            }

            for(int z = 0; z < e; z++){
                w.push_back(i);
                v.push_back(vi);
            }
            if(sum==(2000)/i) break;

        }

    }


    for(int i = 0; i <= w.size(); i++) dp[0][i]=0;
    for(int i = 0; i <= S; i++) dp[i][0]=0;

    for(int i = 1; i <= S; i++){
        for(int j = 1; j < w.size(); j++){
            if(i-w[j]<0) dp[i][j]=dp[i][j-1];
            else{
                dp[i][j]=max(dp[i][j-1], dp[i-w[j]][j-1]+v[j]);
            }
        }
    }
    cout << dp[S][w.size()-1];
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int j = 0; j < vk[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~
knapsack.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0; i <= w.size(); i++) dp[0][i]=0;
      |                    ~~^~~~~~~~~~~
knapsack.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j = 1; j < w.size(); j++){
      |                        ~~^~~~~~~~~~

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