Submission #495620

#TimeUsernameProblemLanguageResultExecution timeMemory
495620pooyashamsCloud Computing (CEOI18_clo)C++14
100 / 100
1664 ms3656 KiB
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 4010;
const int maxs = maxn*50;
const ll inf = 1e17;

struct evnt
{
	int c, f, v;
	evnt(){};
	evnt(int _c, int _f, int _v)
	{
		c = _c;
		f = _f;
		v = _v;
	}
	inline bool operator<(evnt& o)
	{
		if(f == o.f)
			return v < o.v;
		return f > o.f;
	}
} events[maxn];

ll dp[2][maxs];

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	for(int i = 0; i < n; i++)
	{
		int c, f, v; cin >> c >> f >> v;
		events[i] = evnt(+c, f, -v);
	}
	int m; cin >> m;
	for(int i = n; i < n+m; i++)
	{
		int c, f, v; cin >> c >> f >> v;
		events[i] = evnt(-c, f, +v);
	}
	sort(events, events+n+m);
	fill(dp[0], dp[0]+maxs, -inf);
	fill(dp[1], dp[1]+maxs, -inf);
	if(events[0].v < 0)
		dp[0][events[0].c] = events[0].v;
	dp[0][0] = 0;
	ll ans = 0;
	for(int i = 1; i < n+m; i++)
	{
		int c = events[i].c;
		int v = events[i].v;
		for(int j = 0; j < maxs; j++)
		{
			dp[i&1][j] = dp[!(i&1)][j];
			if(c <= j and j-c < maxs)
				dp[i&1][j] = max(dp[i&1][j], dp[!(i&1)][j-c]+v);
			ans = max(ans, dp[i&1][j]);
		}
	}
	cout << ans << endl;
	return 0;
}
#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...