Submission #645505

#	Time	Username	Problem	Language	Result	Execution time	Memory
645505		ymm	Knapsack (NOI18_knapsack)	C++17	100 / 100	556 ms	10824 KiB

knapsack

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#define MAX(x, y) ((x)>(y)?(x):(y))
const int N = 100'010;
const int S = 2048;
pii a[N*30];
int ans[S];
int n, m;
int s;

__attribute__((optimize("O3,unroll-loops"),target("avx")))
void up(int v, int w)
{
	LoopR (i,w,S)
		ans[i] = MAX(ans[i], ans[i-w] + v);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> s >> n;
	Loop (i,0,n) {
		int v, w, k;
		cin >> v >> w >> k;
		k = min(k, s/w);
		while (k) {
			a[m++] = {v, w};
			if (k%2 == 0)
				a[m++] = {v, w};
			v *= 2;
			w *= 2;
			k = (k-1)/2;
		}
	}
	Loop (i,0,m) {
		auto [v, w] = a[i];
		up(v, w);
	}
	int ans = 0;
	Loop (i,0,s+1)
		ans = max(ans, ::ans[i]);
	cout << ans << '\n';
}

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