10A

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> towns;
vector<vector<int>> dp;
vector<vector<int>> pochta;
vector<int> pref;
int bar(int start, int finish) {
    int med = (start + finish-1)/2;
    pochta[start][finish] = med;
    return towns[med]*(2*med-start-finish+1) - (pref[med+1]-pref[start]) + (pref[finish]-pref[med]);
}


int main() {
    int n, m;
    cin >> n >> m;
    towns.resize(n);
    for (auto &x: towns) {
        cin >> x;
    }
    pref.resize(n+1);
    for(int i = 1; i <= n; i++){
        pref[i] = pref[i-1] + towns[i-1];
    }
    pochta.resize(n+1, vector<int>(n+1));
    dp.resize(n+1, vector<int>(m + 1, 100'000'000));
    vector<vector<pair<int, int>>> last(n+1, vector<pair<int,int>>(m+1));
    for (int i = 0; i <= n; i++) {
        dp[i][1] = bar(0, i);
    }
    for (int k = 2; k <= m; k++) {
        for (int n1 = 0; n1 <= n; n1++) {
            for (int p = k-1; p < n1; p++) {
//                dp[n1][k] = min(dp[p][k - 1] + bar(p, n1), dp[n1][k]);
                if (dp[p][k - 1] + bar(p, n1) < dp[n1][k]){
                    dp[n1][k] = dp[p][k - 1] + bar(p, n1);
                    last[n1][k] = {p, k-1};
                }
            }
        }
    }
    cout << dp[n][m] << "\n";
    vector<int>answer;
    pair<int,int> next = last[n][m];
    int p = n;
    while(next.second != 0){
        int finish = p;
        p = next.first;
        answer.push_back(towns[pochta[p][finish]]);
        next = last[next.first][next.second];
    }
    answer.push_back(towns[pochta[0][p]]);
    reverse(answer.begin(), answer.end());
    for (auto x : answer){
        cout << x << " ";
    }
}