Submission #646202

#	Time	Username	Problem	Language	Result	Execution time	Memory
646202		ymm	Cloud Computing (CEOI18_clo)	C++17	18 / 100	1550 ms	3036 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;

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];
core comp_cores[N*C];
int pre_paid_core[N*C];
ll dp[2][N*C];
int n, m;
int cnt_cores;

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

void prepare_input()
{
	sort(comps, comps+n, cmp_comp);
	sort(custs, custs+m, cmp_comp);
	Loop (i,0,n) {
		auto [c, f, v] = comps[i];
		int lst_paid = cnt_cores-1;
		Loop(_,0,c) {
			comp_cores[cnt_cores] = {f, 0};
			pre_paid_core[cnt_cores] = lst_paid;
			++cnt_cores;
		}
		comp_cores[cnt_cores-1].v = v;
	}
}

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

void update_dp(int cus, int cor)
{
	--cus; --cor;
	const int cus2 = cus&1;
	Smax(dp[!cus2][cor+1], dp[!cus2][pre_paid_core[cor]+1]); // no comp
	Smax(dp[!cus2][cor+1], dp[cus2][cor+1]); // no cust
	if (cor+1 < custs[cus].c)
		return;
	ll profit = custs[cus].v;
	int rem = custs[cus].c;
	int cur_cor = cor;
	for (;;) {
		if (comp_cores[cur_cor].f < custs[cus].f)
			return;
		profit -= comp_cores[cur_cor].v;
		int this_cores = cur_cor - pre_paid_core[cur_cor];
		if (rem > this_cores) {
			rem -= this_cores;
			cur_cor -= this_cores;
		} else {
			cur_cor -= rem;
			break;
		}
	}
	Smax(dp[!cus2][cor+1], dp[cus2][cur_cor+1] + profit);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	read_input();
	prepare_input();
	Loop (cus,0,m) {
		const int cus2 = cus&1;
		memset(dp[!cus2], 0, sizeof(dp[!cus2]));
		Loop (cor,0,cnt_cores) {
			update_dp(cus+1, cor+1);
		}
	}
	cout << dp[m&1][cnt_cores] << '\n';
}

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