제출 #1290139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290139		AbdullahIshfaq	Knapsack (NOI18_knapsack)	C++20	100 / 100	558 ms	584 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
void solve()
{
	int s, n, dp[2005], v, w, k;
	cin >> s >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> v >> w >> k;
		for (int r = 0; r < w; r++)
		{
			int dq[2005][2], head = 0, tail = 0, q = 0;
			for (int j = r; j <= s; j += w)
			{
				int mn = min(q, k);
				while (tail - head > 0 and dq[head][1] < q - mn)
				{
					head++;
				}
				while (tail - head > 0 and dq[tail - 1][0] <= dp[j] - q * v)
				{
					tail--;
				}
				dq[tail][0] = dp[j] - q * v;
				dq[tail][1] = q;
				tail++;
				dp[j] = dq[head][0] + q * v;
				q++;
			}
		}
	}
	cout << dp[s] << '\n';
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t = 1;
	// cin >> t;
	for (ll i = 1; i <= t; i++)
	{
		solve();
	}
}

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