제출 #70963

#제출 시각아이디문제언어결과실행 시간메모리
70963MatheusLealVCloud Computing (CEOI18_clo)C++17
100 / 100
988 ms2332 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...