Submission #540569

#	Time	Username	Problem	Language	Result	Execution time	Memory
540569		ac2hu	Knapsack (NOI18_knapsack)	C++14	73 / 100	1095 ms	102304 KiB

knapsack

#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
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);
                while(iitems[i][2] > 0){
                        int lg = log2(iitems[i][2]);
                        iitems[i][2] -= (1 << lg);
                        deb(i, lg);
                        items.push_back({iitems[i][0], iitems[i][1], 1});
                        for(int mask =0;mask<lg;mask++){
                                items.push_back({iitems[i][0]*(1 << mask), iitems[i][1]*(1 << mask), (1 << mask)});
                        }
                }
        }
        deb(items);
        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:31:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int i = 0;i<items.size();i++){
      |                       ~^~~~~~~~~~~~~
knapsack.cpp:13:13: warning: unused variable 'll' [-Wunused-variable]
   13 |         int ll = ceil(log2(s));
      |             ^~

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