Submission #550562

#	Time	Username	Problem	Language	Result	Execution time	Memory
550562		blue	Cloud Computing (CEOI18_clo)	C++17	100 / 100	354 ms	1392 KiB

clo

#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 >= 0; i--)
			{
				dp[i] = max(dp[i], dp[i - e.c] - e.v);
			}
		}
		else
		{
			for(int i = 0; i + e.c <= cores; 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';
}

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