Submission #540568

#	Time	Username	Problem	Language	Result	Execution time	Memory
540568		ac2hu	Knapsack (NOI18_knapsack)	C++14	17 / 100	4 ms	340 KiB

knapsack

#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
signed main() {
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
        int s,n;cin >> s >> n;
        int ll = ceil(log2(s));
        vector<array<int,3>> iitems(n);
        vector<array<int,3>> items;
        for(int i = 0;i<n;i++){
                for(int j = 0;j<3;j++)cin >> iitems[i][j];
                iitems[i][2] = min(iitems[i][2], s);
                int lg = log2(iitems[i][2]);
                for(int mask =0;mask<=lg;mask++){
                        items.push_back({iitems[i][0]*(1 << mask), iitems[i][1]*(1 << mask), 1});
                }
        }
        vector<int> old((int)2e3 + 10), ne((int)2e3 + 10);
        for(int i = 0;i<items.size();i++){
                swap(old, ne);
                for(int j = 1;j<=s;j++){
                        ne[j] = max(old[j], ne[j - 1]);
                        if(j >= items[i][1])
                                ne[j] = max(ne[j], old[j - items[i][1]] + items[i][0]); 
                }
        }
        cout << ne[s] << "\n";
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i = 0;i<items.size();i++){
      |                       ~^~~~~~~~~~~~~
knapsack.cpp:12:13: warning: unused variable 'll' [-Wunused-variable]
   12 |         int ll = ceil(log2(s));
      |             ^~

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