Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 1010;
const int MAXK = 10;
const long long INF = 0x3FFFFFFFFFFFFFFFLL;

int rot;
int N, K;
long long A[MAXN];
long long DP[MAXK][MAXN];
long long WSUM[MAXN][MAXN];

static int madd(int x, int y) {
    x += y;
    if (x >= N) {
        x -= N;
    }
    return x;
}

static long long wsum(int a, int b) {
    return WSUM[madd(a, rot)][madd(b, N - a)];
}

static void solve(int k, int ia, int ib, int ja, int jb) {
    if (ia == ib) {
        return;
    }

    int i = (ia + ib) / 2;
    int arg_j = -1;

    DP[k][i] = INF;
    for (int j = max(i + 1, ja); j < jb; j++) {
        long long v = wsum(i, j) + DP[k - 1][j];
        if (v < DP[k][i]) {
            arg_j = j;
            DP[k][i] = v;
        }
    }

    solve(k, ia, i, ja, arg_j + 1);
    solve(k, i + 1, ib, arg_j, jb);
}

int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    reverse(A, A + N);

    for (int i = 0; i < N; i++) {
        long long sm = 0;
        for (int j = 1; j <= N; j++) {
            WSUM[i][j] = WSUM[i][j - 1] + sm;
            sm += A[madd(i, j - 1)];
        }
    }

    long long result = INF;
    memset(DP, 0x3F, sizeof(DP));
    DP[0][N] = 0;
    for (rot = 0; rot < N; rot++) {
        for (int i = 1; i <= K; i++) {
            solve(i, 0, N, 1, N + 1);
        }
        result = min(result, DP[K][0]);
    }
    cout << result << endl;
}