Submission #540574

#	Time	Username	Problem	Language	Result	Execution time	Memory
540574		ac2hu	Knapsack (NOI18_knapsack)	C++14	73 / 100	1086 ms	53544 KiB

knapsack

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

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