Circular barn - USACO - Convex Hull Trick

//Make CSP great again
//You're as beautiful as the day I lost you
#include <bits/stdc++.h>
#define TASK "cbarn"
using namespace std;
const int N = 1e3, K = 7;
const long long oo = 1e18;
int a[2 * N + 1], n, k;
long long b[N + 1], p[N + 1],res = oo;
void read()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        a[n + i] = a[i];
    }
}
struct Convex
{
    long long dp[N + 1];
    long long A(int i)
    {
        return -(i - 1);
    }
    long long B(int i)
    {
        return dp[i - 1] - p[i - 1] + (i - 1) * b[i - 1];
    }
    long long C(int i)
    {
        return p[i];
    }
    long double Inter(int x, int y)
    {
        return (long double)(B(y) - B(x))/(A(x) - A(y));
    }
    vector<long double> Point;
    vector<int> Line;
    bool ok(int i)
    {
        return Inter(i, Line.back()) > Inter(i, Line[Line.size() - 2]);
    }
    void Init()
    {
        fill(dp, dp + n + 1, oo);
        Point.clear();
        Line.clear();
    }
    void add(int i)
    {
        while(Line.size() > 1 && !ok(i))
        {
            Point.pop_back();
            Line.pop_back();
        }
        if (Line.empty())
        {
            Point.push_back(-1e18);
        }
        else
        {
            Point.push_back(Inter(i, Line.back()));
        }
        Line.push_back(i);
    }
    long long Get(int i)
    {
        int j = upper_bound(Point.begin(), Point.end(), (long double)(b[i])) - Point.begin() - 1;
        return A(Line[j]) * b[i] + B(Line[j]) + C(i);
    }
};
Convex CHT[K + 1];
//dp[i][j] = min(dp[i][j], dp[h - 1][j - 1] + (p[i] - p[h - 1])- (h - 1) * (b[i] - b[h - 1]));
void Update(int x)
{
    long long f[K + 1];
    for (int j = 1; j <= k; ++ j)
    {
        CHT[j].Init();
    }
    CHT[1].dp[0] = 0;
    for (int i = 1; i <= n; ++ i)
    {
        b[i] = b[i - 1] + a[x];
        p[i] = p[i - 1] + 1LL * (i - 1) * a[x];
        //cerr << a[x] << ' ';
        ++x;
    }
    CHT[1].add(1);
    for (int i = 2; i <= n; ++ i)
    {
         CHT[1].dp[i] = p[i];
         f[1] = p[i];
         for (int j = 2; j <= min(i, k); ++ j)
         {
             CHT[j - 1].add(i - 1);
             f[j] = CHT[j - 1].Get(i);
             CHT[j].dp[i] = f[j];
         }
    }
    res = min(res, f[k]);
}
void solve()
{
    for (int i = 1; i <= n; ++ i)
    {
        Update(i);
    }
    cout << res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".in", "r"))
    {
        freopen(TASK".in", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}