Submission #1172354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172354		nagibator	Knapsack (NOI18_knapsack)	C++20	49 / 100	343 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
#define nn '\n'
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define sec second
#define vec std::vector
using namespace std;

const int N = 2005;
vec<pair<int, int>> p;
int dp[N];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m ;
	cin >> n >> m;
	int ans = 0;
	int ok = 0;
	if(m == 1)
	{
		int a, b, c;
		cin >>a >> b >> c;
		while(n > 0 && c > 0)
		{
			if(n < b)
			{
				break;
			}
			n-=b;
			ans+=a;
			c--;
		}
		cout << ans;
	}
	else
	{
		for (int i = 0; i < m; i++) {
			int a, b, c;
			cin >> a>> b >> c;
			while(c--)
			{
				p.pb({a, b});
			}
		}
		for(auto [v, w] : p) {
				for (int j = n ; j >= w; j--) {
					dp[j] = max(dp[j], dp[j - w] + v);
				}
		}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans;
	}
}

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