Submission #673584

#	Time	Username	Problem	Language	Result	Execution time	Memory
673584		dayalk	Knapsack (NOI18_knapsack)	C++14	73 / 100	1086 ms	3960 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr(a, b) for (int i = a; i < b; i++)
#define rep(i, a, b) for (int i = a; i < b; i++)
#define mod 1000000007
#define inf (1LL << 60)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll, pair<ll, ll>>
#define goog(tno) cout << "Case #" << tno << ": "
#define fast_io                       \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL)
#define read(x) \
	int x;      \
	cin >> x
using namespace std;

int main()
{
	fast_io;
	int t = 1;
	// cin >> t;
	while (t--)
	{
		int s, n;
		cin >> s >> n;
		ll v[n], w[n], k[n];
		fr(0, n) cin >> v[i] >> w[i] >> k[i];
		ll dp[s + 1];
		dp[0] = 0;
		memset(dp, 0, sizeof dp);
		fr(0, n)
		{
			for (int j = s; j >= 0; j--)
			{
				rep(r, 1, k[i] + 1)
				{
					if (j + r * w[i] > s)
						break;
					dp[j + r * w[i]] = max(dp[j] + r * v[i], dp[j + r * w[i]]);
				}
			}
		}
		ll res = 0;
		// for (int i = 0; i < s; i++)
		// 	cout << dp[i] << " ";
		// // fr(0, s + 1)
		// // {
		// // 	cout << dp[i] << " ";
		// // }
		fr(0, s + 1) res = max(res, dp[i]);
		cout << res;
	}
	return 0;
}

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