제출 #1283893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283893		arashmemar	Knapsack (NOI18_knapsack)	C++20	0 / 100	5 ms	1600 KiB

knapsack

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

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

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

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

void upd(int ind, long long int x, 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(int ind)
{
	if (q[ind].size())
	{
		return q[ind].front().first;
	}
	return -inf;
}

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

int main()
{
	int s, n;
	cin >> s >> n;
	for (int i = 1;i <= n;i++)
	{
		cin >> v[i] >> w[i] >> k[i];
	}

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

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

		for (int i = s;i >= 0;i--)
		{
			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 (int i = 0;i <= s;i++)
	{
		ans = max(ans, dp[i]);
	}
	cout << ans;
}

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