Submission #1064637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064637		sssamui	Cloud Computing (CEOI18_clo)	C++17	100 / 100	878 ms	1440 KiB

clo

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;

const ll NEGINF = -1e18;

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

	int n;
	cin >> n;
	vector<pair<int, pair<int, ll>>> transac(0);
	while (n--)
	{
		int a, b;
		ll c;
		cin >> a >> b >> c;
		transac.push_back({ b, {a, -c} });
	}

	cin >> n;
	while (n--)
	{
		int a, b;
		ll c;
		cin >> a >> b >> c;
		transac.push_back({ b, {-a, c} });
	}

	sort(transac.begin(), transac.end());
	vector<ll> dp(1e5 + 1, NEGINF);
	dp[0] = 0;
	while (!transac.empty())
	{
		int numtadd = transac.back().second.first;
		ll ptadd = transac.back().second.second;
		transac.pop_back();
		if (numtadd > 0) for (int inord = 1e5 - numtadd; inord > -1; inord--) dp[numtadd + inord] = fmax(dp[numtadd + inord], dp[inord] + ptadd);
		else for (int inord = -numtadd; inord <= 1e5; inord++) dp[numtadd + inord] = fmax(dp[numtadd + inord], dp[inord] + ptadd);
	}

	ll ans = 0;
	for (int inord = 0; inord <= 1e5; inord++) ans = fmax(ans, dp[inord]);
	cout << ans;
}

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