#include <bits/stdc++.h> #pragma GCC Optimize("unroll-loops") #pragma GCC Optimize("O3") #pragma GCC target("sse4,avx2,fma,avx") #define FOR(i, x, y) for (int i = x; i < y; i++) typedef long long ll; using namespace std; const int MAXN = 5e5 + 1; struct Node { ll up, down, dp; Node operator+(Node B) { return {max(up, B.up), max(down, B.down), max(dp, B.dp)}; } }; struct Fair { ll t, l, m; }; bool operator<(Fair A, Fair B) { if (A.t == B.t) return A.l < B.l; return A.t < B.t; } ll n, u, d, s; Fair fairs[MAXN]; ll prelims[MAXN], up[MAXN], down[MAXN]; Node segtree[4 * MAXN]; void build(int node = 1, int l = 1, int r = MAXN) { if (l == r) { if (l == s) segtree[node] = {-l * u, l * d, 0}; else segtree[node] = {(ll)INT_MIN - l * u, (ll)INT_MIN + l * d, (ll)INT_MIN}; } else { int mid = (l + r) / 2; build(node * 2, l, mid); build(node * 2 + 1, mid + 1, r); segtree[node] = segtree[node * 2] + segtree[node * 2 + 1]; } } void update(int pos, int val, int node = 1, int l = 1, int r = MAXN) { if (l == r) { segtree[node] = {segtree[node].up - segtree[node].dp + val, segtree[node].down - segtree[node].dp + val, val}; } else { int mid = (l + r) / 2; if (pos > mid) update(pos, val, node * 2 + 1, mid + 1, r); else update(pos, val, node * 2, l, mid); segtree[node] = segtree[node * 2] + segtree[node * 2 + 1]; } } Node query(int a, int b, int node = 1, int l = 1, int r = MAXN) { if (l > b || r < a || a > b) return {LLONG_MIN, LLONG_MIN, LLONG_MIN}; if (l >= a && r <= b) return segtree[node]; int mid = (l + r) / 2; return query(a, b, node * 2, l, mid) + query(a, b, node * 2 + 1, mid + 1, r); } inline ll cost(ll from, ll to) { if (from > to) return u * (from - to); return d * (to - from); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> u >> d >> s; FOR(i, 0, n) cin >> fairs[i].t >> fairs[i].l >> fairs[i].m; sort(fairs, fairs + n); build(); FOR(i, 0, n) { int first = i++; while (i < n && fairs[i].l == fairs[first].l) i++; int last = --i; FOR(j, first, last + 1) { Node l = query(1, fairs[j].l), r = query(fairs[j].l + 1, MAXN); prelims[j] = max(l.down - fairs[j].l * d, r.up + fairs[j].l * u) + fairs[j].m; } up[last] = prelims[last]; for (int j = last - 1; j >= first; j--) { up[j] = max(prelims[j], up[j + 1] - cost(fairs[j + 1].l, fairs[j].l) + fairs[j].m); } down[first] = prelims[first]; for (int j = first + 1; j <= last; j++) { down[j] = max(prelims[j], down[j - 1] - cost(fairs[j - 1].l, fairs[j].l) + fairs[j].m); } FOR(j, first, last + 1) update(fairs[j].l, max(up[j], down[j])); } Node l = query(1, s), r = query(s + 1, MAXN); cout << max(l.down - s * d, r.up + s * u); return 0; }

salesman.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("unroll-loops")
 
salesman.cpp:3:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")