[Spoj] NKLEAVES - Leaves

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : NKLEAVES - Leaves
Source            : Spoj
Category          : DP Optimization
Algorithm         : DP Optimization - Convex Hull Trick (Offline)
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll          long long
 
struct CHT
{
    vector <ll> m, b;
 
    /**
    Conditions for delete line-2
    1. m[1] >= m[2] >= .... >= m[i-1] >= m[i] and Minimum Query, then
       (f1,f3)x < (f1,f2)x, bad(sz-3, sz-2, sz-1), x[] increasing
    2. m[1] >= m[2] >= .... >= m[i-1] >= m[i] and Maximum Query, then
       (f1,f3)x > (f1,f2)x, bad(sz-1, sz-2, sz-3), x[] decreasing
 
    3. m[1] <= m[2] <= .... <= m[i-1] <= m[i] and Maximum Query, then
       (f1,f3)x < (f1,f2)x, bad(sz-3, sz-2, sz-1), x[] increasing
 
    4. m[1] <= m[2] <= .... <= m[i-1] <= m[i] and Minimum Query, then
       (f1,f3)x > (f1,f2)x, bad(sz-1, sz-2, sz-3), x[] decreasing
 
    If x[] isn't monotonic, then do Ternary Search or keep intersections and do Binary Search.
    **/
 
    bool bad(int f1, int f2, int f3) // returns intersect(f1, f3) <= intersect(f1, f2)
    {
        return 1.0 * (b[f3] - b[f1]) * (m[f1] - m[f2]) <= 1.0 * (b[f2] - b[f1]) * (m[f1] - m[f3]);
    }
    void add(ll mm, ll bb)
    {
        m.emplace_back(mm);
        b.emplace_back(bb);
        int sz = m.size();
        while (sz >= 3 && bad(sz-3, sz-2, sz-1))
        {
            m.erase(m.end() - 2);
            b.erase(b.end() - 2);
            sz--;
        }
    }
    ll f(int i, ll x)
    {
        return m[i] * x + b[i];
    }
//    ll query(ll x) // when x[] is monotonic
//    {
//        if (ptr >= m.size()) ptr = m.size() - 1;
//        while (ptr < m.size()-1 && f(ptr+1, x) < f(ptr, x)) ptr++;
//        return f(ptr, x);
//    }
    ll query(ll x) // when x[] isn't monotonic
    {
        int lo = 0;
        int hi = m.size() - 1;
        while (true)
        {
            if (hi-lo < 3)
            {
                ll min1 = f(lo, x);
                ll min2 = f(hi, x);
                ll min3 = 1e18;
                if (lo+1 < hi) min3 = f(lo+1, x);
                return min(min1, min(min2, min3));
            }
            int mid1 = lo + (hi - lo) / 3;
            int mid2 = hi - (hi - lo) / 3;
            ll y1 = f(mid1, x);
            ll y2 = f(mid2, x);
            if (y1 <= y2) hi = mid2;
            else lo = mid1;
        }
    }
    void Clear()
    {
        m.clear();
        b.clear();
    }
} cht;
 
static const int maxn = 2e5 + 5;
 
int N, K;
ll dp[15][maxn];
ll p[maxn], s[maxn], arr[maxn];
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++)
    {
        scanf("%lld", arr+i);
        p[i] = p[i-1] + arr[i];
        s[i] = s[i-1] + i * arr[i];
    }
    for (int i = 1; i <= N; i++) dp[1][i] = s[i] - s[1] - p[i] + p[1];
    for (int k = 2; k <= K; k++)
    {
        cht.Clear();
        cht.add(0, 0);
        for (int i = 1; i <= N; i++)
        {
            dp[k][i] = cht.query(p[i]) + s[i];
            cht.add(-(i+1), dp[k-1][i] - s[i] + (i+1) * p[i]);
        }
    }
    printf("%lld\n", dp[K][N]);
}