Submission #1064602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064602		sssamui	Cloud Computing (CEOI18_clo)	C++17	36 / 100	3076 ms	1432 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());
	set<int> poss, negposs;
	poss.insert(0), negposs.insert(0);
	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 : negposs)
			{
				dp[numtadd - inord] = fmax(dp[numtadd - inord], dp[-inord] + ptadd);
				for (int inord : negposs) poss.insert(numtadd - inord);
			}

			for (int inord : poss) negposs.insert(-inord);
		}

		else
		{
			for (int inord : poss) if (numtadd + inord > -1)
			{
				dp[numtadd + inord] = fmax(dp[numtadd + inord], dp[inord] + ptadd);
				negposs.insert(-numtadd - inord);
			}

			for (int inord : negposs) poss.insert(-inord);
		}
	}

	ll ans = 0;
	for (int inord : poss) ans = fmax(ans, dp[inord]);
	cout << ans;
}

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