Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <queue>
- #define task "SALES"
- using namespace std;
- using ll = long long;
- using ld = long double;
- const int N = 5e5 + 2;
- int n;
- ll u, d, s, sum[N];
- ll dp[N], f[N];
- const ll Inf = 1e16;
- struct fes
- {
- ll t, m, l;
- bool operator<(const fes &a) const
- {
- return t < a.t || (t == a.t && l < a.l);
- }
- } a[N];
- #define BIT(i, x) (((x) >> (i)) & 1)
- struct Trie
- {
- Trie *child[2];
- ll v;
- Trie()
- {
- child[0] = child[1] = NULL;
- v = -Inf;
- }
- ll getlow(int id, int x)
- {
- if (id == -1)
- {
- return v;
- }
- if (BIT(id, x))
- {
- ll ans = -Inf;
- if (child[0])
- ans = max(ans, child[0]->v);
- if (child[1])
- ans = max(ans, child[1]->getlow(id - 1, x));
- return ans;
- }
- else
- {
- if (child[0])
- return child[0]->getlow(id - 1, x);
- return -Inf;
- }
- }
- ll getup(int id, int x)
- {
- if (id == -1)
- {
- return v;
- }
- if (BIT(id, x))
- {
- if (child[1])
- return child[1]->getup(id - 1, x);
- return -Inf;
- }
- else
- {
- ll ans = -Inf;
- if (child[1])
- ans = max(ans, child[1]->v);
- if (child[0])
- ans = max(ans, child[0]->getup(id - 1, x));
- return ans;
- }
- }
- } lower, upper;
- void Add(Trie *a, int x, ll v)
- {
- int id = 18;
- while (1)
- {
- if (id == -1)
- {
- a->v = max(a->v, v);
- return;
- }
- if (!(a->child[BIT(id, x)]))
- a->child[BIT(id, x)] = new Trie;
- a->v = max(a->v, v);
- a = a->child[BIT(id, x)];
- --id;
- }
- }
- void Read()
- {
- cin >> n >> u >> d >> s;
- for (int i = 1; i <= n; ++i)
- cin >> a[i].t >> a[i].l >> a[i].m;
- sort(a + 1, a + n + 1);
- for (int i = 1; i <= n; ++i)
- sum[i] = sum[i - 1] + a[i].m;
- }
- void Solve()
- {
- /// BASE CASE
- Add(&lower, s, s * d);
- Add(&upper, s, -u * s);
- /// END BASE CASE
- for (int i = 1; i <= n; ++i)
- {
- int j = i;
- while (j <= n && a[i].t == a[j].t)
- ++j;
- /// Calculate f[]
- for (int t = i; t < j; ++t)
- {
- f[t] = max(lower.getlow(18, a[t].l) - d * a[t].l,
- upper.getup(18, a[t].l) + u * a[t].l);
- }
- /// Calculate dp[]
- ll ilr(-Inf), irl(-Inf), pilr(-Inf), pirl(-Inf);
- for (int t = i; t < j; ++t)
- {
- pilr = max(pilr, -(u + d) * a[t].l - sum[t - 1]);
- pirl = max(pirl, -u * a[t].l - sum[t - 1]);
- ilr = max(ilr, u * a[t].l + f[t] + pilr);
- irl = max(irl, f[t] - d * a[t].l + pirl);
- dp[t] = max(d * a[t].l + ilr,
- (u + d) * a[t].l + irl) +
- sum[t];
- }
- /// Update lower, upper
- for (int t = i; t < j; ++t)
- {
- Add(&lower, a[t].l, dp[t] + d * a[t].l);
- Add(&upper, a[t].l, dp[t] - u * a[t].l);
- }
- i = j - 1;
- }
- cout << max(lower.getlow(18, s) - d * s, upper.getup(18, s) + u * s);
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- freopen(task ".INP", "r", stdin),
- freopen(task ".OUT", "w", stdout);
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment