#include <bits/stdc++.h> using namespace std; const int N = 500005, m = 500001, INF = 1000000009; struct ban { int t, x, m; }; bool operator<(const ban& a, const ban& b) { return a.t < b.t; } bool so1(const ban& a, const ban& b) { return a.x < b.x; } int n; int d, u; int s; ban a[N]; vector<int> t1, t2; void ubd(vector<int>& t, int tl, int tr, int l, int r, int b, int k, int pos) { if (l > r) return; if (tl == l && tr == r) { t[pos] = max(t[pos], b); return; } int m = (tl + tr) / 2; ubd(t, tl, m, l, min(m, r), b, k, pos * 2); ubd(t, m + 1, tr, max(m + 1, l), r, b, k, pos * 2 + 1); } int qry(vector<int>& t, int tl, int tr, int x, int k, int pos) { if (tl == tr) { return t[pos] + (k * x); } int m = (tl + tr) / 2; if (x <= m) return max(qry(t, tl, m, x, k, pos * 2), t[pos] + (k * x)); else return max(qry(t, m + 1, tr, x, k, pos * 2 + 1), t[pos] + (k * x)); } void solv1() { sort(a + 1, a + n + 1); t1.assign(4 * N, -INF); t2.assign(4 * N, -INF); ubd(t1, 1, m, 1, s, -s * d, d, 1); ubd(t2, 1, m, s, m, s * u, -u, 1); for (int i = 1; i <= n; ++i) { int ans = max(qry(t1, 1, m, a[i].x, d, 1), qry(t2, 1, m, a[i].x, -u, 1)) + a[i].m; ubd(t1, 1, m, 1, a[i].x, ans - a[i].x * d, d, 1); ubd(t2, 1, m, a[i].x, m, ans + a[i].x * u, -u, 1); } int ans = max(qry(t1, 1, m, s, d, 1), qry(t2, 1, m, s, -u, 1)); printf("%d\n", ans); } vector<ban> v[N]; vector<int> ansv[N]; int main() { //freopen("input.txt", "r", stdin); scanf("%d%d%d%d", &n, &d, &u, &s); for (int i = 1; i <= n; ++i) scanf("%d%d%d", &a[i].t, &a[i].x, &a[i].m); //solv1(); for (int i = 1; i <= n; ++i) v[a[i].t].push_back(a[i]); t1.assign(4 * N, -INF); t2.assign(4 * N, -INF); ubd(t1, 1, m, 1, s, -s * d, d, 1); ubd(t2, 1, m, s, m, s * u, -u, 1); for (int i = 1; i < N; ++i) { sort(v[i].begin(), v[i].end(), so1); ansv[i].assign(v[i].size(), -INF); int yans = -INF; for (int j = 0; j < v[i].size(); ++j) { if (j) yans -= (v[i][j].x - v[i][j - 1].x) * u; int yansv = -INF; yansv = max(qry(t1, 1, m, v[i][j].x, d, 1), qry(t2, 1, m, v[i][j].x, -u, 1)) + v[i][j].m; yansv = max(yansv, yans + v[i][j].m); yans = max(yans, yansv); ansv[i][j] = max(ansv[i][j], yansv); } yans = -INF; for (int j = (int)v[i].size() - 1; j >= 0; --j) { if (j != (int)v[i].size() - 1) yans -= (v[i][j + 1].x - v[i][j].x) * d; int yansv = -INF; yansv = max(qry(t1, 1, m, v[i][j].x, d, 1), qry(t2, 1, m, v[i][j].x, -u, 1)) + v[i][j].m; yansv = max(yansv, yans + v[i][j].m); yans = max(yans, yansv); ansv[i][j] = max(ansv[i][j], yansv); } for (int j = 0; j < v[i].size(); ++j) { int ans = ansv[i][j];//max(qry(t1, 1, m, a[i].x, d, 1), qry(t2, 1, m, a[i].x, -u, 1)) + a[i].m; ubd(t1, 1, m, 1, v[i][j].x, ans - v[i][j].x * d, d, 1); ubd(t2, 1, m, v[i][j].x, m, ans + v[i][j].x * u, -u, 1); } } int ans = max(qry(t1, 1, m, s, d, 1), qry(t2, 1, m, s, -u, 1)); printf("%d\n", ans); return 0; }

salesman.cpp: In function 'int main()':
salesman.cpp:87:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
salesman.cpp:108:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
salesman.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &d, &u, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].t, &a[i].x, &a[i].m);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~