Submission #997424

#	Time	Username	Problem	Language	Result	Execution time	Memory
997424		mostafa133	Cloud Computing (CEOI18_clo)	C++14	100 / 100	327 ms	1372 KiB

clo

#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 fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const ll mod = 998244353;
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;
}

vector<vector<char>> v;
vector<vector<ll>> a;
ll n, m;
void dfs(ll i, ll j, ll k)
{
	if (i < 0 || i >= n || j < 0 || j >= m || a[i][j] || v[i][j] == '.')
	{
		return;
	}
	a[i][j] = k;
	dfs(i + 1, j, k), dfs(i - 1, j, k), dfs(i, j + 1, k), dfs(i, j - 1, k);
}
int main()
{
	fast;
	// freopen("pails.in", "r", stdin);
	// freopen("pails.out", "w", stdout);
	ll t = 1;
	// cin >> t;
	while (t--)
	{
		ll n, m;
		cin >> n;
		vector<array<ll, 3>> a(n);
		ll s1 = 0, s2 = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> a[i][1] >> a[i][0] >> a[i][2];
			s1 += a[i][1];
		}
		sort(all(a), greater<array<ll, 3>>());
		cin >> m;
		vector<array<ll, 3>> b(m);
		for (int i = 0; i < m; i++)
		{
			cin >> b[i][1] >> b[i][0] >> b[i][2];
			s2 += b[i][1];
		}
		sort(all(b), greater<>());
		vector<ll> dp(max(s2, s1) + 1, LLONG_MIN/4);
		ll in = 0;
		dp[0]=0;
		for (int i = 0; i < m; i++)
		{
			while (in < n && b[i][0] <= a[in][0])
			{
				for (int j = dp.size() - 1; j >= a[in][1]; j--)
				{
					dp[j] = max(dp[j], dp[j - a[in][1]] - a[in][2]);
				}
				in++;
			}
			for (int j = 0; j < dp.size()-b[i][1]; j++)
			{
				dp[j] = max(dp[j], dp[j + b[i][1]] + b[i][2]);
			}
		}
		// for(int i = 0; i < dp.size())
		cout << *max_element(all(dp)) << '\n';
	}
	return 0;
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   91 |    for (int j = 0; j < dp.size()-b[i][1]; j++)

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10