제출 #470720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470720		prvocislo	Cloud Computing (CEOI18_clo)	C++17	100 / 100	2693 ms	5832 KiB

clo

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

struct vec { int c, f, v; };
bool cmp(const vec& a, const vec& b) { return a.f > b.f; }
const int maxc = 55;
const ll inf = 1e18;
void upd(ll& a, const ll& b) { a = max(a, b); }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<vec> p(n);
	for (int i = 0; i < n; i++) cin >> p[i].c >> p[i].f >> p[i].v;
	sort(p.begin(), p.end(), cmp);
	int m;
	cin >> m;
	vector<vec> z(m);
	for (int i = 0; i < m; i++) cin >> z[i].c >> z[i].f >> z[i].v;
	sort(z.begin(), z.end(), cmp);
	vector<vector<vector<ll> > > dp(2, vector<vector<ll>>(m + 1, vector<ll>(maxc * 2, -inf)));
	// dp[dalsi pocitac & 1][dalsi zakaznik][pocet pocitacov navyse]
	dp[0][0][0] = 0;
	ll ans = -inf;
	for (int i = 0; i < n; i++)
	{
		int pv = (i & 1), nw = pv ^ 1;
		for (int j = 0; j <= m; j++) for (int c = 0; c < maxc * 2; c++)
			dp[nw][j][c] = -inf;
		// najprv vyskusame kupit/nekupit novy pocitac
		for (int j = 0; j < m; j++) for (int c = 0; c < maxc; c++)
		{
			upd(dp[nw][j][c], dp[pv][j][c]);
			upd(dp[nw][j][c + p[i].c], dp[pv][j][c] - p[i].v);
		}
		// teraz vyskusame ze predame/nepredame jadra zakaznikovi
		for (int j = 0; j < m; j++) for (int c = 0; c < maxc * 2; c++)
		{
			upd(dp[nw][j + 1][c], dp[nw][j][c]);
			if (z[j].c <= c && z[j].f <= p[i].f)
				upd(dp[nw][j + 1][c - z[j].c], dp[nw][j][c] + z[j].v);
		}
		// teraz ideme updatnut ans
		for (int j = 0; j <= m; j++) for (int c = 0; c < maxc * 2; c++)
			upd(ans, dp[nw][j][c]);
	}
	cout << ans << "\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