제출 #646210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646210		ymm	Cloud Computing (CEOI18_clo)	C++17	100 / 100	1461 ms	3720 KiB

clo

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#pragma GCC optimize("O3")

struct core {
	int f, v;
};
struct comp {
	int c, f, v;
};
bool cmp_comp(const comp &a, const comp &b)
{
	return a.f < b.f;
}

const int N = 2010;
const int C = 52;
comp custs[N], comps[N];
ll dp[2][N][C*2];
int n, m;

void read_input()
{
	cin >> n;
	Loop (i,0,n) {
		auto &[c, f, v] = comps[i];
		cin >> c >> f >> v;
	}
	cin >> m;
	Loop (i,0,m) {
		auto &[c, f, v] = custs[i];
		cin >> c >> f >> v;
	}
	sort(comps, comps+n, cmp_comp);
	sort(custs, custs+m, cmp_comp);
}

template<class T>
void Smax(T &x, const T &y)
{
	x = max(x, y);
}

void update_dp(int cus, int com, int used)
{
	--cus; --com;
	const int cus2 = cus&1;
	Smax(dp[!cus2][com+1][used], dp[!cus2][com][min(C, used)]);
	if (used >= C)
		Smax(dp[!cus2][com+1][used], dp[cus2][com+1][used]);
	if (comps[com].f < custs[cus].f)
		return;
	int remc_com = comps[com].c - max(0, used-C);
	int remc_cus = custs[cus].c - max(0, C-used);
	ll profit =   (used >= C? custs[cus].v: 0) 
	            - (used <= C? comps[com].v: 0);
	if        (remc_com > remc_cus) {
		int new_used = C + (comps[com].c - (remc_com - remc_cus));
		Smax(dp[!cus2][com+1][    used],
		     dp[ cus2][com+1][new_used] + profit);
	} else if (remc_com < remc_cus) {
		int new_used = C - (custs[cus].c - (remc_cus - remc_com));
		Smax(dp[!cus2][com+1][    used],
		     dp[!cus2][com  ][new_used] + profit);
	} else {
		Smax(dp[!cus2][com+1][used],
		     dp[ cus2][com  ][   C] + profit);
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	read_input();
	memset(dp[0], -32 /* -inf */, sizeof(dp[0]));
	dp[0][0][C] = 0;
	Loop (com,0,n) Loop (used,0,comps[com].c)
		dp[0][com+1][used + C] = 0;
	Loop (cus,0,m) {
		const int cus2 = cus&1;
		memset(dp[!cus2], -32 /* -inf */, sizeof(dp[!cus2]));
		dp[!cus2][0][C] = 0;
		Loop (com,0,n) Loop(used, -custs[cus].c + 1, comps[com].c) {
			update_dp(cus+1, com+1, C + used);
		}
	}
	cout << dp[m&1][n][C] << '\n';
}

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