fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long 
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1e5;
  9. const int maxk = 20;
  10. const ll INF = 1e18;
  11.  
  12. struct Segment_Tree
  13. {
  14.     int n;
  15.     vector<ll> tree, lazy;
  16.  
  17.     Segment_Tree(int n = 0) : n(n)
  18.     {
  19.         tree.assign(4 * n + 10, 0);
  20.         lazy.assign(4 * n + 10, 0);
  21.     }
  22.     void push(int id)
  23.     {
  24.         if (lazy[id] == 0)
  25.             return ;
  26.         for (int nid = id * 2; nid <= id * 2 + 1; nid++)
  27.         {
  28.             tree[nid] += lazy[id];
  29.             lazy[nid] += lazy[id];
  30.         }
  31.         lazy[id] = 0;
  32.     }
  33.     void update(int id, int l, int r, int u, int v, ll val)
  34.     {
  35.         if (r < u || l > v)
  36.             return ;
  37.         if (u <= l && r <= v)
  38.             return tree[id] += val, lazy[id] += val, void();
  39.         int m = l + r >> 1;
  40.         push(id);
  41.         update(id << 1, l, m, u, v, val);
  42.         update(id << 1 | 1, m + 1, r, u, v, val);
  43.         tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
  44.     }
  45.     ll get(int id, int l, int r, int u, int v)
  46.     {
  47.         if (r < u || l > v)
  48.             return -INF;
  49.         if (u <= l && r <= v)
  50.             return tree[id];
  51.         int m = l + r >> 1;
  52.         push(id);
  53.         return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
  54.     }
  55.     void update(int l, int r, ll val)
  56.     {
  57.         update(1, 0, n, l, r, val);
  58.     }
  59.     ll get(int l, int r)
  60.     {
  61.         return get(1, 0, n, l, r);
  62.     }
  63.     void print_tree(int id, int l, int r)
  64.     {
  65.         if (l == r)
  66.             return cout << tree[id] << ' ', void();
  67.         int m = l + r >> 1;
  68.         push(id);
  69.         print_tree(id << 1, l, m);
  70.         print_tree(id << 1 | 1, m + 1, r);
  71.     }
  72. };
  73.  
  74. int n, k;
  75. ll dp[maxk + 10][maxn + 10], a[maxn + 10], b[maxn + 10];
  76. Segment_Tree st;
  77. vector<int> st_min, st_max;
  78.  
  79. int main()
  80. {
  81.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  82.     if (fopen("MAXIMIZE.INP", "r"))
  83.     {
  84.         freopen("MAXIMIZE.INP", "r", stdin);
  85.         freopen("MAXIMIZE.OUT", "w", stdout);
  86.     }
  87.  
  88.     cin >> n >> k;
  89.     for (int i = 1; i <= n; i++)
  90.     {
  91.         cin >> a[i];
  92.         b[i] = a[i];
  93.     }
  94.     a[0] = INF;
  95.     b[0] = -INF;
  96.     for (int j = 0; j <= k; j++)
  97.         for (int i = 0; i <= n; i++)
  98.             dp[j][i] = -INF;
  99.     dp[0][0] = 0;
  100.     for (int j = 1; j <= k; j++)
  101.     {
  102.         st = Segment_Tree(n);
  103.         st_min.clear();
  104.         st_max.clear();
  105.         st_min.push_back(0);
  106.         st_max.push_back(0);
  107.         for (int i = 1; i <= n; i++)
  108.         {
  109.             while (st_max.size() >= 2 && a[st_max.back()] <= a[i])
  110.             {
  111.                 int r = st_max.back();
  112.                 st_max.pop_back();
  113.                 int l = st_max.back() + 1;
  114.                 st.update(l - 1, r - 1, -a[r]);
  115.             }
  116.             while (st_min.size() >= 2 && a[st_min.back()] >= a[i])
  117.             {
  118.                 int r = st_min.back();
  119.                 st_min.pop_back();
  120.                 int l = st_min.back() + 1;
  121.                 st.update(l - 1, r - 1, -a[r]);
  122.             }
  123.             st.update(st_max.back(), i - 1, a[i]);
  124.             st.update(st_min.back(), i - 1, a[i]);
  125.             st.update(i - 1, i - 1, dp[j - 1][i - 1]);
  126.             dp[j][i] = st.get(0, i - 1);
  127.             st_max.push_back(i);
  128.             st_min.push_back(i);
  129.             // st.print_tree(1, 0, n);
  130.             // el;
  131.             // cout << dp[j][i] << ' ';
  132.         }
  133.         // el;
  134.     }
  135.     cout << dp[k][n];
  136. }
  137.  
Success #stdin #stdout 0s 5604KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/5Woinr
language:
C++14 (gcc 8.3)
created:
20 hours ago
visibility:
public

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!