Submission #645504

#	Time	Username	Problem	Language	Result	Execution time	Memory
645504		ymm	Knapsack (NOI18_knapsack)	C++17	100 / 100	425 ms	12128 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;

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("avx2")))
void up32(int v, int w, int l)
{
	typedef int ymm __attribute((vector_size(32),aligned(4)));
	for (int i = 2040; i >= l; i -= 8)
		*(ymm*)(ans+i) = __builtin_ia32_pmaxsd256(*(ymm*)(ans+i), *(ymm*)(ans+i-w) + v);
}
void up(int v, int w)
{
	int l = w%8?w+8-w%8:w;
	up32(v, w, l);
	LoopR (i,w,l)
		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