Dang_Quan_10_Tin

SALES

Aug 27th, 2020 (edited)
282
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <queue>
  5. #define task "SALES"
  6. using namespace std;
  7. using ll = long long;
  8. using ld = long double;
  9.  
  10. const int N = 5e5 + 2;
  11. int n;
  12. ll u, d, s, sum[N];
  13. ll dp[N], f[N];
  14. const ll Inf = 1e16;
  15. struct fes
  16. {
  17.     ll t, m, l;
  18.     bool operator<(const fes &a) const
  19.     {
  20.         return t < a.t || (t == a.t && l < a.l);
  21.     }
  22. } a[N];
  23.  
  24. #define BIT(i, x) (((x) >> (i)) & 1)
  25.  
  26. struct Trie
  27. {
  28.     Trie *child[2];
  29.     ll v;
  30.     Trie()
  31.     {
  32.         child[0] = child[1] = NULL;
  33.         v = -Inf;
  34.     }
  35.     ll getlow(int id, int x)
  36.     {
  37.         if (id == -1)
  38.         {
  39.             return v;
  40.         }
  41.         if (BIT(id, x))
  42.         {
  43.             ll ans = -Inf;
  44.             if (child[0])
  45.                 ans = max(ans, child[0]->v);
  46.             if (child[1])
  47.                 ans = max(ans, child[1]->getlow(id - 1, x));
  48.             return ans;
  49.         }
  50.         else
  51.         {
  52.             if (child[0])
  53.                 return child[0]->getlow(id - 1, x);
  54.             return -Inf;
  55.         }
  56.     }
  57.     ll getup(int id, int x)
  58.     {
  59.         if (id == -1)
  60.         {
  61.             return v;
  62.         }
  63.         if (BIT(id, x))
  64.         {
  65.             if (child[1])
  66.                 return child[1]->getup(id - 1, x);
  67.             return -Inf;
  68.         }
  69.         else
  70.         {
  71.             ll ans = -Inf;
  72.             if (child[1])
  73.                 ans = max(ans, child[1]->v);
  74.             if (child[0])
  75.                 ans = max(ans, child[0]->getup(id - 1, x));
  76.             return ans;
  77.         }
  78.     }
  79. } lower, upper;
  80.  
  81. void Add(Trie *a, int x, ll v)
  82. {
  83.     int id = 18;
  84.     while (1)
  85.     {
  86.         if (id == -1)
  87.         {
  88.             a->v = max(a->v, v);
  89.             return;
  90.         }
  91.         if (!(a->child[BIT(id, x)]))
  92.             a->child[BIT(id, x)] = new Trie;
  93.         a->v = max(a->v, v);
  94.         a = a->child[BIT(id, x)];
  95.         --id;
  96.     }
  97. }
  98.  
  99. void Read()
  100. {
  101.     cin >> n >> u >> d >> s;
  102.     for (int i = 1; i <= n; ++i)
  103.         cin >> a[i].t >> a[i].l >> a[i].m;
  104.     sort(a + 1, a + n + 1);
  105.     for (int i = 1; i <= n; ++i)
  106.         sum[i] = sum[i - 1] + a[i].m;
  107. }
  108.  
  109. void Solve()
  110. {
  111.     /// BASE CASE
  112.     Add(&lower, s, s * d);
  113.     Add(&upper, s, -u * s);
  114.     /// END BASE CASE
  115.     for (int i = 1; i <= n; ++i)
  116.     {
  117.         int j = i;
  118.         while (j <= n && a[i].t == a[j].t)
  119.             ++j;
  120.         /// Calculate f[]
  121.         for (int t = i; t < j; ++t)
  122.         {
  123.             f[t] = max(lower.getlow(18, a[t].l) - d * a[t].l,
  124.                        upper.getup(18, a[t].l) + u * a[t].l);
  125.         }
  126.         /// Calculate dp[]
  127.         ll ilr(-Inf), irl(-Inf), pilr(-Inf), pirl(-Inf);
  128.         for (int t = i; t < j; ++t)
  129.         {
  130.             pilr = max(pilr, -(u + d) * a[t].l - sum[t - 1]);
  131.             pirl = max(pirl, -u * a[t].l - sum[t - 1]);
  132.             ilr = max(ilr, u * a[t].l + f[t] + pilr);
  133.             irl = max(irl, f[t] - d * a[t].l + pirl);
  134.             dp[t] = max(d * a[t].l + ilr,
  135.                         (u + d) * a[t].l + irl) +
  136.                     sum[t];
  137.         }
  138.         /// Update lower, upper
  139.         for (int t = i; t < j; ++t)
  140.         {
  141.             Add(&lower, a[t].l, dp[t] + d * a[t].l);
  142.             Add(&upper, a[t].l, dp[t] - u * a[t].l);
  143.         }
  144.         i = j - 1;
  145.     }
  146.     cout << max(lower.getlow(18, s) - d * s, upper.getup(18, s) + u * s);
  147. }
  148.  
  149. int32_t main()
  150. {
  151.     ios::sync_with_stdio(0);
  152.     cin.tie(0);
  153.     cout.tie(0);
  154.     if (fopen(task ".INP", "r"))
  155.         freopen(task ".INP", "r", stdin),
  156.             freopen(task ".OUT", "w", stdout);
  157.     Read();
  158.     Solve();
  159. }
Advertisement
Add Comment
Please, Sign In to add comment