Advertisement
umnov

Untitled

Feb 22nd, 2019
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define cerr if (false) cerr
  6.  
  7. #define int long long
  8.  
  9. const int inf = 1e18 + 239;
  10.  
  11. namespace LeeChaoTree {
  12. struct Line {
  13. int k;
  14. int b;
  15.  
  16. Line() {
  17. k = 0;
  18. b = -inf;
  19. }
  20.  
  21. Line(int k_, int b_) {
  22. k = k_;
  23. b = b_;
  24. }
  25.  
  26. int get_val(int x) {
  27. return k * x + b;
  28. }
  29. };
  30.  
  31. int sz;
  32. vector<Line> t;
  33.  
  34. void modify(int v, int l, int r, Line to) {
  35. int m = (r + l) >> 1;
  36. int lp = (to.get_val(l) > t[v].get_val(l));
  37. int rp = (to.get_val(m) > t[v].get_val(m));
  38. if (rp) {
  39. swap(t[v], to);
  40. }
  41. if (l + 1 == r) {
  42. return;
  43. }
  44. if (lp != rp) {
  45. modify(2 * v + 1, l, m, to);
  46. } else {
  47. modify(2 * v + 2, m, r, to);
  48. }
  49. }
  50.  
  51. int query(int v, int l, int r, int pos) {
  52. if (l + 1 == r) {
  53. return t[v].get_val(pos);
  54. } else {
  55. int m = (r + l) >> 1;
  56. int cur = t[v].get_val(pos);
  57. int qr = inf;
  58. if (pos < m) {
  59. qr = query(2 * v + 1, l, m, pos);
  60. } else {
  61. qr = query(2 * v + 2, m, r, pos);
  62. }
  63. return max(cur, qr);
  64. }
  65. }
  66.  
  67. void add_line(int k, int b) {
  68. cerr << "LINE " << k << ' ' << b << '\n';
  69. Line to = Line(k, b);
  70. modify(0, 0, sz, to);
  71. }
  72.  
  73. int get_val(int x) {
  74. return query(0, 0, sz, x);
  75. }
  76.  
  77. void build(int sz_) {
  78. sz = sz_;
  79. t.resize(4 * sz);
  80. }
  81.  
  82. // vector<Line> t;
  83. //
  84. // void add_line(int k, int b) {
  85. // cerr << "LINE " << k << ' ' << b << '\n';
  86. // Line to = Line(k, b);
  87. // t.push_back(to);
  88. // }
  89. //
  90. // int get_val(int x) {
  91. // int best = -inf;
  92. // for (auto y : t) {
  93. // best = max(best, y.get_val(x));
  94. // }
  95. // return best;
  96. // }
  97. //
  98. // void build(int sz_) {
  99. //
  100. // }
  101. }
  102. signed main() {
  103. ios_base::sync_with_stdio(false);
  104. cin.tie(0);
  105.  
  106. #ifdef LOCAL
  107. freopen("input.txt", "r", stdin);
  108. freopen("output.txt", "w", stdout);
  109. #endif
  110.  
  111. //dp[i] - в момент i(i не приняли)
  112. //dp[i], приняли j
  113. //dp[i] = dp[j] + a[j] - b[j] * (i - j)
  114. //dp[i] = dp[j] + a[j] - b[j] * i + b[j] * j
  115. //dp[i] = - i * (b[j]) + (dp[j] + a[j] + b[j] * j)
  116. //k = - b[j], b = dp[j] + a[j] + b[j] * j
  117.  
  118. int n;
  119. cin >> n;
  120. vector<int> a(n);
  121. vector<int> d(n);
  122. for (int i = 0; i < n; i++) {
  123. cin >> a[i] >> d[i];
  124. }
  125.  
  126. vector<int> dp(n + 1);
  127. dp[0] = 0;
  128. LeeChaoTree::build(n + 1);
  129. LeeChaoTree::add_line(-d[0], dp[0] + a[0] + d[0] * 0);
  130. for (int i = 1; i <= n; i++) {
  131. auto val = LeeChaoTree::get_val(i);
  132. dp[i] = max((int)0, val);
  133. if (i < n) {
  134. LeeChaoTree::add_line(-d[i], dp[i] + a[i] + d[i] * i);
  135. }
  136. }
  137. for (int i = 0; i <= n; i++) {
  138. cerr << dp[i] << ' ';
  139. }
  140. cout << dp[n];
  141.  
  142. // vector<int> dp(n + 1);
  143. // dp[0] = 0;
  144. // for (int i = 1; i <= n; i++) {
  145. // for (int j = 0; j < i; j++) {
  146. // dp[i] = max(dp[i], - i * (d[j]) + (dp[j] + a[j] + d[j] * j));
  147. // }
  148. // }
  149. // for (int i = 0; i <= n; i++) {
  150. // cerr << dp[i] << ' ';
  151. // }
  152. // cout << dp[n];
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement