#include #include #include using namespace std; const int MAX_T = 5e5, MAX_L = 5e5 + 1; const int INF = 2e9 + 1e8; // Fenwick Tree (for prefix max) void update(vector &fenwick, int index, int value) { while (index < (int)fenwick.size()) { fenwick[index] = max(fenwick[index], value); index += index & -index; } } int getMax(const vector &fenwick, int index) { int mx = -INF; while (index) { mx = max(mx, fenwick[index]); index -= index & -index; } return mx; } // Reverse Fenwick Tree (for suffix max) void updateR(vector &fenwick, int index, int value) { update(fenwick, (int)fenwick.size()-index, value); } int getMaxR(const vector &fenwick, int index) { return getMax(fenwick, (int)fenwick.size()-index); } vector> fairsOnDay[1+MAX_T+1]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, U, D, S; cin >> n >> U >> D >> S; // since you start and end at one place, only U+D matters D += U, U = 0; D = -D; // profit of D, D is negative for (int i = 0; i < n; ++i) { int t, l, m; cin >> t >> l >> m; fairsOnDay[t].emplace_back(l, m); } fairsOnDay[MAX_T+1].emplace_back(S, 0); // Define p[k] as the maximum profit after visiting a fair at location k up to time t vector maxP(1+MAX_L, -INF), maxDif(1+MAX_L, -INF); // two fenwick trees, one for max p[k] on suffix, one for max p[k] - D*k on prefix update(maxDif, S, 0 - D*S); updateR(maxP, S, 0); for (int t = 0; t <= MAX_T+1; ++t) { if (fairsOnDay[t].empty()) continue; int c = fairsOnDay[t].size(); sort(fairsOnDay[t].begin(), fairsOnDay[t].end()); // sort by location vector maxProfit(c, -INF); // after visiting this fair, without visiting any other fairs at time t for (int i = 0; i < c; ++i) { auto [l, m] = fairsOnDay[t][i]; // arrive from upstream // maximum over all k <= l of m + D(l-k) + p[k] maxProfit[i] = max(maxProfit[i], m + D*l + getMax(maxDif, l)); // add max of (p[k] - D*k) on prefix // arrive from downstream // maximum over all k >= l of m + p[k] maxProfit[i] = max(maxProfit[i], m + getMaxR(maxP, l)); // add max of p[k] on suffix } // now consider moving between fairs on this day vector downstream(c), upstream(c); // moving downstream or upstream for (int i = 0; i < c; ++i) { downstream[i] = maxProfit[i]; if (i) { auto [l, m] = fairsOnDay[t][i]; int l2 = fairsOnDay[t][i-1].first; downstream[i] = max(downstream[i], downstream[i-1] + D*(l-l2) + m); } } for (int i = c-1; i >= 0; --i) { upstream[i] = maxProfit[i]; if (i < c-1) { int m = fairsOnDay[t][i].second; upstream[i] = max(upstream[i], upstream[i+1] + m); } } for (int i = 0; i < c; ++i) maxProfit[i] = max({maxProfit[i], downstream[i], upstream[i]}); if (t == MAX_T+1) cout << maxProfit[0] << endl; else { // update data structures for (int i = 0; i < c; ++i) { auto [l, m] = fairsOnDay[t][i]; update(maxDif, l, maxProfit[i] - D*l); updateR(maxP, l, maxProfit[i]); } } } return 0; }