제출 #550567

#제출 시각아이디문제언어결과실행 시간메모리
550567blueCloud Computing (CEOI18_clo)C++17
100 / 100
376 ms1356 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vll = vector<ll>;

struct event
{
	int c;
	ll f;
	ll v;

	int t;
};

bool operator < (event A, event B)
{
	if(A.f == B.f) return A.t < B.t;
	else return A.f > B.f;
}

const int cores = 100'000;
const ll INF = 1'000'000'000'000'000'000LL;

int main()
{
	vector<event> E;

	int n;
	cin >> n;

	for(int i = 0; i < n; i++)
	{
		int c, f, v;
		cin >> c >> f >> v;
		E.push_back({c, f, v, 0});
	}

	int m;
	cin >> m;

	for(int j = 0; j < m; j++)
	{
		int c, f, v;
		cin >> c >> f >> v;
		E.push_back({c, f, v, 1});
	}

	sort(E.begin(), E.end());

	vll dp(1+cores, -INF);
	dp[0] = 0;

	for(auto e : E)
	{
		if(e.t == 0)
		{
			for(int i = cores; i >= e.c; i--)
			{
				dp[i] = max(dp[i], dp[i - e.c] - e.v);
			}
		}
		else
		{
			for(int i = 0; i <= cores - e.c; i++)
			{
				dp[i] = max(dp[i], dp[i + e.c] + e.v);
			}
		}
	}

	ll res = 0;
	for(int i = 0; i <= cores; i++)
		res = max(res, dp[i]);

	cout << res << '\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...