Submission #500790

#	Time	Username	Problem	Language	Result	Execution time	Memory
500790		pooty	Knapsack (NOI18_knapsack)	C++17	100 / 100	75 ms	7084 KiB

knapsack

#define REP(i, n) for(int i = 0; i < n; i ++)
#define REPL(i,m, n) for(int i = m; i < n; i ++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define M_PI 3.1415926535897932384
#define INF 999999999
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int s,n;cin>>s>>n;
	vll varr(n);
	vi warr(n);
	vi karr(n);
	map<int, vector<pair<long long, int>>> mpping;
	REP(i, n) {
		cin>>varr[i]>>warr[i]>>karr[i];
		mpping[warr[i]].push_back({varr[i], karr[i]});
	}
	vll flyingtable(s+1, 0);
	for (auto [w, arr] : mpping) {
		sort(arr.begin(), arr.end(), greater<pair<ll, int>>());
		vll newtable = flyingtable;
		REP(j, s+1) {
			int totw = j;
			ll curex = flyingtable[j];
			auto it = arr.begin();
			while (it != arr.end()) {
				auto [val, ct] = *it;
				while (ct > 0) {
					curex += val;
					totw += w;
					ct--;
					if (totw > s) {
						goto done;
					}
					newtable[totw] = max(newtable[totw], curex);
				} 
				it = next(it);
			} 
			done:
			continue;
		}
		swap(flyingtable, newtable);
	}
	ll curmx = 0;
	REP(i, s+1) {
		curmx = max(curmx, flyingtable[i]);
	}cout<<curmx;
}

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