제출 #1286781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286781		arashmemar	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	4108 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

const long long int maxn = 1e5 + 100, maxs = 2010, inf = 2e16 + 10;

deque <pair <long long int, long long int>> q[maxs];

long long int dp[maxs], cnt[maxs];

void upd(long long int ind, long long int x, long long int k)
{
	while (q[ind].size() and x > q[ind].back().first)
	{
		q[ind].pop_back();
	}
	q[ind].push_back({x, ++cnt[ind]});
	if (q[ind].front().second == cnt[ind] - k)
	{
		q[ind].pop_front();
	}
	return ;
}

long long int get(long long int ind)
{
	if (q[ind].size())
	{
		return q[ind].front().first;
	}
	return -inf;
}

long long int v[maxn], w[maxn], k[maxn];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long int s, n;
	cin >> s >> n;
	for (long long int i = 1;i <= n;i++)
	{
		cin >> v[i] >> w[i] >> k[i];
	}

	for (long long int i = 0;i < maxs;i++)
	{
		dp[i] = -inf;
	}
	dp[s] = 0;
	for (long long int j = 1;j <= n;j++)
	{

		for (long long int i = 0;i <= s;i++)
		{
			cnt[i] = 0;
			q[i].clear();
		}

		for (long long int i = s;i >= 0;i--)
		{
			long long int back = dp[i];
			dp[i] = max(dp[i], get(i % w[j]) + v[j] * cnt[i % w[j]]);
			upd(i % w[j], back - v[j] * (cnt[i % w[j]]), k[j]);
		}
	}

	long long int ans = 0;
	for (long long int i = 0;i <= s;i++)
	{
		ans = max(ans, dp[i]);
	}
	cout << ans;
}

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