Submission #1266714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266714		WH8	Knapsack (NOI18_knapsack)	C++20	100 / 100	88 ms	6540 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define int long long 
#define pll pair<int, int>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);

int32_t main(){
	//~ FASTIO
	int s, n; cin >> s>>n;
	int valt[n+1], weit[n+1], numt[n+1];
	int val[n+1], wei[n+1], num[n+1];
	int st[n]; iloop(1, n+1) st[i-1] = i;
	iloop(0, n) {
		cin >> valt[i+1] >> weit[i+1]>> numt[i+1];
		//~ cin  >> weit[i+1]>> valt[i+1];// >> numt[i+1];
	}
	wei[0] = -1;
	sort(st, st+n, [&](int a, int b){
		if (weit[a] == weit[b]){
			return valt[a] > valt[b];
		}
		else return weit[a] < weit[b];
	});
	//iloop(0, n) cout << st[i] << " "; 

	iloop(1, n+1){
		val[i] = valt[st[i-1]];
		wei[i] = weit[st[i-1]];
		num[i] = numt[st[i-1]];
	}
	//~ for(int i=1;i<=n;i++){
		//~ cout<<val[i]<<" "<<wei[i]<<" "<<num[i]<<"\n";
	//~ }
	int csm = 0;
	vector<pll> items;
	iloop(1, n+1){
		if (wei[i] != wei[i-1]) {
			csm = 0;
		}
		while (csm <= s and num[i]){
			items.pb({wei[i], val[i]});
			num[i]--, csm+=wei[i];
		}
	}
	int mem[2005];
	fill(mem, mem+2005, 0);
	//~ for(auto [w,v]:items){
		//~ printf("%lld %lld\n",w,v);
	//~ }
	/*iloop(1, u+1){
		cout << endl<<  i << " " << wgt[i] << endl;
		for (auto it : hm[i]) cout << it << " ";
		cout << endl;
	}
	dg(u);*/
	
	for(auto [w, v] : items){
		for(int j=s;j>=1;j--){
			mem[j]=max(mem[j], (j-w >=0?mem[j-w]+v:0));
		}
	}
	/*iloop(0, u+1){
		jloop(0, s+1) cout << mem[i][j] << " ";
		cout << endl;
	}*/
	cout << mem[s];
}

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