Submission #257650

#	Time	Username	Problem	Language	Result	Execution time	Memory
257650		Berted	Cloud Computing (CEOI18_clo)	C++14	100 / 100	1558 ms	3712 KiB

clo

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair<int, int>
#define ppi pair<int, pii>
#define fst first
#define snd second
using namespace std;

const ll INF = 1e16;

int n, m;
ll dp[2][2001][101] = {};
vector<ppi> comp, pers;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int c, f, v; cin >> c >> f >> v;
		comp.push_back({f, {c, v}});
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int c, f, v; cin >> c >> f >> v;
		pers.push_back({f, {c, v}});
	}
	sort(comp.begin(), comp.end(), greater<ppi>());
	sort(pers.begin(), pers.end(), greater<ppi>());
	
	for (int i = 0; i <= m; i++)
	{
		for (int j = 0; j <= 100; j++) dp[0][i][j] = -INF;
	}
	dp[0][0][0] = 0;
	for (int i = 1; i <= n; i++)
	{
		int ci = i & 1, pi = ~i & 1;
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; k <= 100; k++)
			{
				dp[ci][j][k] = dp[pi][j][k];
				if (j) dp[ci][j][k] = max(dp[ci][j][k], dp[ci][j - 1][k]);
				if (k >= comp[i - 1].snd.fst) dp[ci][j][k] = max(dp[ci][j][k], dp[pi][j][k - comp[i - 1].snd.fst] - comp[i - 1].snd.snd);
				if (j && comp[i - 1].fst >= pers[j - 1].fst && k + pers[j - 1].snd.fst <= 100 && dp[ci][j - 1][k + pers[j - 1].snd.fst] > -INF)
				{
					dp[ci][j][k] = max(dp[ci][j][k], dp[ci][j - 1][k + pers[j - 1].snd.fst] + pers[j - 1].snd.snd);
				}
				// cout << i << " " << j << " " << k << " " << dp[ci][j][k] << "\n";
			}
		}
	}
	ll MX = 0;
	for (int k = 0; k <= 100; k++)
	{
		MX = max(MX, dp[n & 1][m][k]);
	}
	cout << MX << "\n";
	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