Expert.
Put your skills to the test.

Problem summary

Partition a positive array into at most K consecutive groups. A group of length L and aggression sum S contributes (L−1)S total fear. Minimize the sum of these costs. Empty aquariums are allowed.

Source clarification. The official full archive contains the integer Lagrangian/Monge optimization; this independent implementation uses a tie-to-more convention to recover the desired group count. Source archive: https://infos.infosbg.com/files/Contests/ETI/2020/A/problems/cancer.zip

Constraints

1≤K≤N≤100000; 1≤Ai≤10000000.

Worked example

Original statement sample.

8 4
8 1 2 3 9 1 9 1

32

Solution analysis

1. Each aggression value is counted once for every other crab in its group, so the group cost is (length−1) times its sum. Prefix sums make that cost an O(1) calculation. Since aggressions are positive, splitting a non-singleton group strictly reduces cost, so an optimum uses exactly K nonempty groups.
2. The ordinary DP is dp[g][i]=min(dp[g−1][j]+cost(j+1,i)). Computing all K layers is too slow. Instead charge a nonnegative penalty λ for each group and minimize originalCost+λ·groupCount in one DP. Larger λ favors fewer groups. On equal penalized cost, consistently prefer the solution with more groups.
3. The segment cost has the Monge property: for overlapping intervals, the cost of their union plus their intersection is at least the sum of the two original costs. The extra terms are nonnegative multiples of sums in the outside portions. Consequently optimal split positions are monotone, and two candidate last-split positions can exchange preference only once as the endpoint increases.
4. Keep candidate split positions in a deque, together with the first endpoint at which each becomes optimal. When inserting a new candidate, binary-search its crossing with the last candidate and remove candidates that never win. Every candidate is inserted and removed at most once; these crossing searches give O(N log N) work for one penalty.
5. The optimal original cost as a function of group count is discretely convex for this Monge segmentation. Binary-search the largest integer penalty whose chosen solution still has at least K groups. At this supporting penalty, subtract λK from the penalized optimum to recover the exact K-group optimum. Preferring more groups on ties is essential at a jump.
6. For the sample, choose [8],[1,2,3],[9,1],[9,1]. Their costs are0,2·6,1·10,1·10, totaling32. A singleton aquarium contributes0; when K=N the result is0 without running the optimization.

Why it works

Prefix sums compute every group cost exactly. The penalty DP examines the same last-split recurrence as ordinary segmentation, and the single-crossing Monge ordering lets the deque discard only candidates that cannot be optimal at any unprocessed endpoint. The Monge uncrossing argument also gives diminishing returns from additional groups, so a supporting penalty exists for every group count; the tie-to-more convention finds its integer boundary. Subtracting λK removes only the artificial penalty and yields the minimum original cost for K groups.

Watch out. This optimization relies on positive values and the Monge cost, not merely on having a partition DP. Do not mix tie conventions between candidate comparisons and penalty search. Keep unused aquariums distinct from nonempty groups; positivity proves exactly K groups suffice. Use long long for costs and penalties.

An independently written complete program with standard headers.

// Key idea: Prefix sums compute every group cost exactly. The penalty DP examines the same last-split
// recurrence as ordinary segmentation, and the single-crossing Monge ordering lets the deque discard
// only candidates that cannot be optimal at any unprocessed endpoint.
#include<algorithm>
#include<deque>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
struct Candidate{
    int split;
    int first;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    int wanted;
    cin>>n>>wanted;
    vector<long long>prefix(n+1);
    for(int i=1;i<=n;i++){
        long long aggression;
        cin>>aggression;
        prefix[i]=prefix[i-1]+aggression;
    }
    if(wanted==n){
        cout<<0<<'\n';
        return 0;
    }
    vector<long long>best(n+1);
    vector<int>groups(n+1);
    auto cost=[&](int split,int end){
        return (end-split-1LL)*(prefix[end]-prefix[split]);
    };
    auto solve=[&](long long penalty){
        best[0]=0;
        groups[0]=0;
        deque<Candidate>candidates;
        candidates.push_back({0,1});
        auto better=[&](int a,int b,int end){
            long long first=best[a]+cost(a,end);
            long long second=best[b]+cost(b,end);
            return first<second||(first==second&&groups[a]>groups[b]);
        };
        for(int end=1;end<=n;end++){
            while(candidates.size()>1&&candidates[1].first<=end){
                candidates.pop_front();
            }
            int split=candidates.front().split;
            best[end]=best[split]+cost(split,end)+penalty;
            groups[end]=groups[split]+1;
            if(end==n){
                continue;
            }
            int starts=end+1;
            bool useful=true;
            while(!candidates.empty()){
                int old=candidates.back().split;
                int left=max(end+1,candidates.back().first);
                if(!better(end,old,n)){
                    useful=false;
                    break;
                }
                if(better(end,old,left)){
                    candidates.pop_back();
                    continue;
                }
                int right=n;
                while(left<right){
                    int middle=(left+right)/2;
                    if(better(end,old,middle)){
                        right=middle;
                    }
                    else{
                        left=middle+1;
                    }
                }
                starts=left;
                break;
            }
            if(useful){
                candidates.push_back({end,starts});
            }
        }
        return pair<long long,int>{best[n],groups[n]};
    };
    long long low=0;
    long long high=(n-1LL)*prefix[n]+1;
    while(low<high){
        long long middle=low+(high-low+1)/2;
        if(solve(middle).second>=wanted){
            low=middle;
        }
        else{
            high=middle-1;
        }
    }
    auto answer=solve(low);
    cout<<answer.first-low*wanted<<'\n';
}