fork(5) download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <sstream>
  4. #include <iomanip>
  5. #include <algorithm>
  6. #include <complex>
  7. #include <locale>
  8. #include <vector>
  9. #include <deque>
  10. #include <queue>
  11. #include <set>
  12. #include <map>
  13. #include <bitset>
  14. using namespace std;
  15. struct line
  16. {
  17.     long long a, b;
  18. };
  19. const int MAXN = 100000, MAXT = 100000, LOGT = 16;
  20. int n, m, t[MAXN + 9], a[MAXN + 9], b[MAXN + 9], id[MAXN + 9];
  21. long long sumA[MAXN + 9], sumB[MAXN + 9], sumBT[MAXN + 9], f[MAXN + 9];
  22. line it[(1 << LOGT + 2) + 9];
  23.  
  24. int Cmp(int x, int y)
  25. {
  26.     return t[x] < t[y];
  27. }
  28.  
  29. long long Get(line d, int pos)
  30. {
  31.     return d.a * pos + d.b;
  32. }
  33.  
  34. long long Query(int x, int low, int high, int pos)
  35. {
  36.     if(low > pos || high < pos)
  37.     {
  38.         return 0;
  39.     }
  40.     long long res = Get(it[x], pos);
  41.     if(low == high)
  42.     {
  43.         return res;
  44.     }
  45.     int mid = (low + high) / 2;
  46.     res = max(res, Query(x * 2, low, mid, pos));
  47.     res = max(res, Query(x * 2 + 1, mid + 1, high, pos));
  48.     return res;
  49. }
  50.  
  51. void Update(int x, int low, int high, line val)
  52. {
  53.     int mid = (low + high) / 2;
  54.     if(Get(val, low) <= Get(it[x], low) && Get(val, high) <= Get(it[x], high))
  55.     {
  56.         return;
  57.     }
  58.     if(Get(val, low) >= Get(it[x], low) && Get(val, high) >= Get(it[x], high))
  59.     {
  60.         it[x] = val;
  61.         return;
  62.     }
  63.     if(Get(val, low) <= Get(it[x], low) && Get(val, mid) <= Get(it[x], mid))
  64.     {
  65.         Update(x * 2 + 1, mid + 1, high, val);
  66.         return;
  67.     }
  68.     if(Get(val, low) >= Get(it[x], low) && Get(val, mid) >= Get(it[x], mid))
  69.     {
  70.         Update(x * 2 + 1, mid + 1, high, it[x]);
  71.         it[x] = val;
  72.         return;
  73.     }
  74.     if(Get(val, mid + 1) <= Get(it[x], mid + 1) && Get(val, high) <= Get(it[x], high))
  75.     {
  76.         Update(x * 2, low, mid, val);
  77.         return;
  78.     }
  79.     if(Get(val, mid + 1) >= Get(it[x], mid + 1) && Get(val, high) >= Get(it[x], high))
  80.     {
  81.         Update(x * 2, low, mid, it[x]);
  82.         it[x] = val;
  83.         return;
  84.     }
  85. }
  86.  
  87. int main()
  88. {
  89.     //ifstream cin("vmpizza.inp");
  90.     //ofstream cout("vmpizza.out");
  91.     ios_base::sync_with_stdio(0);
  92.     cin.tie(NULL);
  93.     cin >> n >> m;
  94.     for(int i = 1; i <= n; i++)
  95.     {
  96.         cin >> t[i] >> a[i] >> b[i];
  97.         id[i] = i;
  98.     }
  99.     sort(id + 1, id + n + 1, Cmp);
  100.     for(int i = 1; i <= n; i++)
  101.     {
  102.         sumA[id[i]] = sumA[id[i - 1]] + a[id[i]];
  103.         sumB[id[i]] = sumB[id[i - 1]] + b[id[i]];
  104.         sumBT[id[i]] = sumBT[id[i - 1]] + (long long)b[id[i]] * t[id[i]];
  105.     }
  106.     for(int i = 1; i <= n; i++)
  107.     {
  108.         int x = id[i];
  109.         f[x] = Query(1, 1, MAXT, t[x]) - m + sumA[x] - (long long)sumB[x] * t[x] + sumBT[x];
  110.         Update(1, 1, MAXT, (line){sumB[x], f[x] - sumA[x] - sumBT[x]});
  111.     }
  112.     cout << f[id[n]] << "\n";
  113.     return 0;
  114. }
  115.  
  116.  
Success #stdin #stdout 0s 12024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ba6ShL
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!