Submission #70963

#	Time	Username	Problem	Language	Result	Execution time	Memory
70963		MatheusLealV	Cloud Computing (CEOI18_clo)	C++17	100 / 100	988 ms	2332 KiB

clo

#include <bits/stdc++.h>
#define N 2010
using namespace std;
typedef long long ll;

struct S
{
	int val, c, f, t;

} v[2*N];

inline bool cmp(S a, S b)
{
	if(a.f != b.f) return a.f > b.f;

	return a.t < b.t;
}

int n, m, soma;

ll dp[2][50*N];

ll solve()
{
	ll A = (n + m + 1)%2, B = (n + m)%2;

	for(int i = n + m + 1; i >= 1; i--)
	{
		for(int C = 0; C <= soma; C++)
		{
			if(i > n + m) dp[A][C] = 0;

			else
			{
				if(v[i].t == 0)
				{
					ll buy = dp[B][C + v[i].c] - (ll)v[i].val;

					ll nop = dp[B][C];

					dp[A][C] = max(buy, nop);	
				}

				else
				{
					ll get = ( v[i].c <= C ? dp[B][C - v[i].c] + (ll)v[i].val : 0);

					ll nop = dp[B][C];

					dp[A][C] = max(nop, get);
				}
			}
		}

		swap(A, B);
	}

	return dp[1][0];
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	for(int i = 1; i <= n; i++) cin>>v[i].c>>v[i].f>>v[i].val, v[i].t = 0, soma += v[i].c;

	cin>>m;

	for(int i = n + 1; i <= n + m; i++) cin>>v[i].c>>v[i].f>>v[i].val, v[i].t = 1;

	sort(v + 1, v + n + m + 1, cmp);

	cout<<solve()<<"\n";
}

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