SHARE
TWEET

Untitled

umnov Feb 22nd, 2019 106 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top