Expert.
Put your skills to the test.

Problem summary

A sidewalk has N unit sections, with V[i] kilograms of leaves at section i. Up to K bags, each initially weighing C, are available at position 0. Moving one section costs the weight currently carried. Leaves can be collected for free, but moving right is allowed only after the current section is empty. Return all leaves in bags to position 0 using minimum effort.

Constraints

1 <= K <= N <= 1000000; 0 <= C <= 10^12; V[i]>=1; sum V[i]<=10^12; 4 seconds; 1024 MB.

Worked example

Original statement sample, using the documented local driver for grader tasks.

7 4 1
4 3 6 8 2 10 1

199

Solution analysis

1. An optimal trip handles a consecutive block of newly reached sections: carrying leaves farther right or revisiting a cleared prefix unnecessarily cannot help. For a block j+1..i, take an empty bag to j, collect while moving right to i, then return. Its effort is 2*i*(C+P[i]-P[j]) - sum_{t=j+1..i} t*V[t], where P is the volume prefix sum. The last sum over all blocks is the fixed constant S=sum t*V[t].
2. Ignoring -S temporarily, a partition has block cost W(j,i)=2*i*(C+P[i]-P[j]). The direct DP over bag count is too slow. Add a nonnegative penalty lambda to every block and solve an unrestricted DP: dp[i]=2*i*(C+P[i])+lambda+min_{j<i}(dp[j]-2*P[j]*i). Every earlier j supplies a line of slope -2*P[j], intercept dp[j]. Positive volumes make slopes strictly decreasing; query positions i increase, so a deque convex hull evaluates one penalty in linear time.
3. Track the number of bags used by each DP state, preferring fewer bags on equal penalized cost. As lambda increases, this count cannot increase. The block cost is Monge: for a<b<c<d, W(a,c)+W(b,d)-W(a,d)-W(b,c)=2*(d-c)*(P[a]-P[b])<=0. The minimum cost as a function of the allowed number of blocks has diminishing improvements, which is the convexity needed by the Aliens optimization.
4. If the zero-penalty optimum uses at most K bags, it already solves the problem. Otherwise binary-search the smallest integer penalty whose optimum uses at most K. The exact K-block optimum is penalizedCost-lambda*K; subtract S. At a tie, adjacent optimal bag counts can straddle K, but the supporting-line identity still gives the K-block cost. A penalty of 2*N*(C+P[N]) suffices to favor one bag.
5. For the sample, the best four-block partition is [1..2],[3..4],[5..6],[7]. Its actual efforts are 22,70,86,21, summing to 199. In hull comparisons, use exact integer arithmetic. Collinear intersections must also compare bag counts, equivalently treating them as infinitesimal intercept perturbations; otherwise tie-breaking can invalidate the penalty search.

Why it works

The route exchange argument reduces optimal collection to consecutive-block partitions, and summing trip costs yields the stated DP plus a fixed constant. The hull computes that DP exactly for each penalty. Monge block costs give a convex sequence of fixed-block optima, so a supporting penalty recovers the requested count when the unrestricted optimum needs more than K. The chosen tie rule makes the binary-search predicate monotone. Therefore the recovered cost is the optimum with at most K bags.

Watch out. The limit is at most K bags, not exactly K when empty bags are expensive. Do not forget the fixed subtraction S. Handle C=0. Bag-count ties must be preserved consistently in both queries and hull redundancy tests. Do not evaluate cross-products in 64-bit arithmetic.

Compile with -DLOCAL for the sample driver; omit it for the judge function. GCC/Clang __int128 is used as an explicit extension for exact hull arithmetic.

#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
namespace Cleanup{
struct Line{
    long long slope;
    long long intercept;
    int bags;
    __int128 value(long long x)const{
        return (__int128)slope*x+intercept;
    }
};
bool noWorse(const Line&first,const Line&second,long long x){
    __int128 a=first.value(x);
    __int128 b=second.value(x);
    return a<b||(a==b&&first.bags<=second.bags);
}
bool redundant(const Line&first,const Line&middle,const Line&last){
    __int128 left=(__int128)(middle.intercept-first.intercept)*(middle.slope-last.slope);
    __int128 right=(__int128)(last.intercept-middle.intercept)*(first.slope-middle.slope);
    if(left!=right){
        return left>right;
    }
    // An infinitesimal positive cost per bag implements exact tie-breaking.
    long long tieLeft=1LL*(middle.bags-first.bags)*(middle.slope-last.slope);
    long long tieRight=1LL*(last.bags-middle.bags)*(first.slope-middle.slope);
    return tieLeft>=tieRight;
}
} // namespace Cleanup
long long solve(const vector<long long>&V,int K,long long C){
    using namespace Cleanup;
    int n=(int)V.size();
    vector<long long>prefix(n+1);
    long long fixedCost=0;
    for(int i=1;i<=n;++i){
        prefix[i]=prefix[i-1]+V[i-1];
        fixedCost+=i*V[i-1];
    }
    vector<Line>hull;
    hull.reserve(n+1);
    auto evaluate=[&](long long penalty){
        hull.clear();
        hull.push_back({0,0,0});
        int head=0;
        long long cost=0;
        int bags=0;
        for(int i=1;i<=n;++i){
            while(head+1<(int)hull.size()&&noWorse(hull[head+1],hull[head],i)){
                ++head;
            }
            __int128 current=hull[head].value(i)+(__int128)2*i*(C+prefix[i])+penalty;
            cost=(long long)current;
            bags=hull[head].bags+1;
            Line line={-2*prefix[i],cost,bags};
            while((int)hull.size()-head>=2&&redundant(hull[hull.size()-2],hull.back(),line)){
                hull.pop_back();
            }
            hull.push_back(line);
        }
        return pair<long long,int>{cost,bags};
    };
    auto unrestricted=evaluate(0);
    if(unrestricted.second<=K){
        return unrestricted.first-fixedCost;
    }
    long long low=0;
    long long high=2LL*n*(C+prefix[n]);
    while(low<high){
        long long middle=low+(high-low)/2;
        if(evaluate(middle).second<=K){
            high=middle;
        }
        else{
            low=middle+1;
        }
    }
    auto optimum=evaluate(low);
    return (long long)((__int128)optimum.first-(__int128)low*K-fixedCost);
}
#ifdef LOCAL
int main(){
    int n;
    int k;
    long long c;
    cin>>n>>k>>c;
    vector<long long>volumes(n);
    for(long long&volume:volumes){
        cin>>volume;
    }
    cout<<solve(volumes,k,c)<<'\n';
}
#endif