salesman.cpp

#include <bits/stdc++.h>

using namespace std;

using llint = long long;

const int MAXN = 1<<19;
const llint INF = 1ll<<60;

struct fair
{
	int t;
	llint l;
	llint m;
} fairs[MAXN];

inline bool operator<(const fair& a, const fair& b)
{
	return make_pair(a.t, a.l) < make_pair(b.t, b.l);
}

llint dp[MAXN];
llint enter[MAXN];
llint up[MAXN];
llint down[MAXN];
int lo[MAXN], hi[MAXN];
llint sum[MAXN];

llint logaU[MAXN], logaD[MAXN];

void addD(int i, llint x)
{
	for (++i; i < MAXN; i += i&-i)
		logaD[i] = max(logaD[i], x);
}

llint getD(int i)
{
	llint ret = -INF;
	for (++i; i; i -= i&-i)
		ret = max(ret, logaD[i]);
	return ret;
}

void addU(int i, llint x)
{
	for (i = MAXN - i - 10; i < MAXN; i += i&-i)
		logaU[i] = max(logaU[i], x);
}

llint getU(int i)
{
	llint ret = -INF;
	for (i = MAXN - i - 10; i; i -= i&-i)
		ret = max(ret, logaU[i]);
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, u, d, s, i;
	llint best;
	
	for (i = 0; i < MAXN; ++i)
		logaU[i] = logaD[i] = -INF;
	
	cin>>n>>u>>d>>s;
	
	for (i = 1; i <= n; ++i)
	{
		cin>>fairs[i].t>>fairs[i].l>>fairs[i].m;
	}
	fairs[0].t = 0;
	fairs[0].l = s;
	fairs[0].m = 0;
	fairs[n + 1].t = MAXN - 10;
	fairs[n + 1].l = s;
	fairs[n + 1].m = 0;
	n += 2;
	sort(fairs, fairs + n);
	
	memset(lo, -1, sizeof lo);
	memset(hi, -1, sizeof hi);
	for (i = 0; i < n; ++i)
	{
		if (lo[fairs[i].t] == -1)
			lo[fairs[i].t] = i;
		hi[fairs[i].t] = i + 1;
	}
	
	addU(s, -s * u);
	addD(s, s * d);
	
	for (int t = 1; t < MAXN; ++t) if (lo[t] != -1)
	{
		for (i = lo[t]; i < hi[t]; ++i)
		{
			enter[i] = max(fairs[i].l * u + getU(fairs[i].l), -fairs[i].l * d + getD(fairs[i].l));
		}
		
		sum[lo[t]] = 0;
		for (i = lo[t]; i < hi[t]; ++i)
		{
			sum[i + 1] = sum[i] + fairs[i].m;
		}
		
		best = -INF;
		for (i = hi[t] - 1; i >= lo[t]; --i)
		{
			best = max(best, enter[i] - fairs[i].l * u);
			up[i] = fairs[i].l * (u + d) - sum[i] + best;
		}
		
		best = -INF;
		for (i = lo[t]; i < hi[t]; ++i)
		{
			best = max(best, enter[i] + fairs[i].l * d);
			down[i] = sum[i + 1] - fairs[i].l * (u + d) + best;
		}
		
		best = -INF;
		for (i = lo[t]; i < hi[t]; ++i)
		{
			best = max(best, up[i]);
			dp[i] = sum[i + 1] - fairs[i].l * d + best;
		}
		
		best = -INF;
		for (i = hi[t] - 1; i >= lo[t]; --i)
		{
			best = max(best, down[i]);
			dp[i] = max(dp[i], fairs[i].l * u - sum[i] + best);
			
			addU(fairs[i].l, dp[i] - fairs[i].l * u);
			addD(fairs[i].l, dp[i] + fairs[i].l * d);
		}
	}
	
	cout<<dp[n - 1]<<'\n';
}