제출 #495620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
495620		pooyashams	Cloud Computing (CEOI18_clo)	C++14	100 / 100	1664 ms	3656 KiB

clo

#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;
}

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