Submission #1084004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084004		mostafa133	Knapsack (NOI18_knapsack)	C++14	100 / 100	93 ms	36328 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define vec vector
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const ll mod = 1e9 + 7;
ld fpow(ll a, ll b, ll m = -1)
{
	if (m != -1)
		a %= m;
	ll res = 1;
	while (b > 0)
	{
		if (b % 2 == 1)
		{
			if (m != -1)
				res = res * a % m;
			else
			{
				res *= a;
			}
		}
		a = a * a;
		if (m != -1)
		{
			a %= m;
		}
		b /= 2;
	}
	return res;
}
int main()
{
	// fast;
	// freopen("pails.in", "r", stdin);
	// freopen("pails.out", "w", stdout);
	ll t = 1;
	// cin >> t;
	while (t--)
	{
		ll n, s;
		cin >> s >> n;
		vec<vec<array<ll, 2>>> v(s + 1);
		for (int i = 0; i < n; i++)
		{
			ll a, b, c;
			cin >> a >> b >> c;
			v[b].push_back({a, c});
		}
		for (int i = 0; i <= s; i++)
		{
			sort(all(v[i]), greater<array<ll, 2>>());
		}
		vec<vec<ll>> dp(s + 1, vec<ll>(s + 1));
		for (int i = 0; i <= s; i++)
		{
			if(i)
			dp[i] = dp[i - 1];
			ll cur = 0, cur2 = 0;
			for (int j = 0; j < v[i].size(); j++)
			{
				for (int ii = 0; ii < v[i][j][1]; ii++)
				{
					cur += v[i][j][0], cur2 += i;
					if (cur2 > s)
					{
						break;
					}
					for (int k = cur2; k <= s; k++)
					{
						dp[i][k] = max(dp[i][k], dp[i - 1][k - cur2] + cur);
					}
				}
				if (cur2 > s)
				{
					break;
				}
			}
		}
		ll mx = 0;
		for (int i = 0; i <= s; i++)
		{
			mx = max(mx, dp[s][i]);
		}
		cout << mx << '\n';
	end:;
	}

	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for (int j = 0; j < v[i].size(); j++)
      |                    ~~^~~~~~~~~~~~~
knapsack.cpp:93:2: warning: label 'end' defined but not used [-Wunused-label]
   93 |  end:;
      |  ^~~

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