[CS Academy] Squared Ends

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Squared Ends
Source            : Codeforces
Category          : Data Structure
Algorithm         : Dynamic Convex Hull Trick
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
#define ll              long long int  
  
static const int maxn = 2e5 + 5;  
  
// Dynamic Convex Hull Trick  
// Keeps upper hull for maximums.  
// add lines with -m and -b and return -ans to get minimums  
// source : https://codeforces.com/blog/entry/11155?#comment-162462  
  
static const ll is_query = LLONG_MIN;  
  
struct Line  
{  
      ll m, b;  
      mutable function <const Line*()> succ;  
      bool operator < (const Line &rhs) const  
      {  
            if (rhs.b != is_query) return m < rhs.m;  
            const Line *s = succ();  
            if (!s) return 0;  
            ll x = rhs.m;  
            return (b - s->b) < ((s->m - m) * x);  
      }  
};  
  
struct CHT : public multiset <Line>  
{  
      bool bad(iterator y)  
      {  
            auto z = next(y);  
            if (y == begin())  
            {  
                  if (z == end()) return 0;  
                  return y->m == z->m && y->b <= z->b;  
            }  
            auto x = prev(y);  
            if (z == end()) return y->m == x->m && y->b <= x->b;  
            return 1.0 * (x->b - y->b) * (z->m - y->m) >= 1.0 * (y->b - z->b) * (y->m - x->m);  
      }  
      void add(ll m, ll b)  
      {  
            auto y = insert({m, b});  
            y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };  
            if (bad(y)) { erase(y); return; }  
            while (next(y) != end() && bad(next(y))) erase(next(y));  
            while (y != begin() && bad(prev(y))) erase(prev(y));  
      }  
      ll query(ll x)  
      {  
            auto l = *lower_bound((Line){x, is_query});  
            return l.m * x + l.b;  
      }  
};  
  
ll sq(ll x)  
{  
      return x * x;  
}  
  
ll dp[105][10005];  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int N, K;  
      cin >> N >> K;  
      vector <ll> arr(N + 1);  
      for (int i = 1; i <= N; i++) cin >> arr[i];  
      for (int i = 1; i <= N; i++) dp[1][i] = sq(arr[i] - arr[1]);  
      for (int k = 2; k <= K; k++)  
      {  
            CHT cht;  
            for (int i = k; i <= N; i++)  
            {  
                  cht.add(1LL * 2 * arr[i], -(1LL * sq(arr[i]) + dp[k - 1][i - 1]));  
                  ll best = -(cht).query(arr[i]) + sq(arr[i]);  
                  dp[k][i] = best;  
            }  
      }  
      cout << dp[K][N] << endl;  
}