#include <bits/stdc++.h>
using namespace std;
struct answer{
long long sum;
int cnt;
bool operator<(answer ot){
if(sum!=ot.sum)
return sum<ot.sum;
return cnt>ot.cnt;
}
};
int const NMAX=300005;
answer dp[NMAX];
int n,k;
int v[NMAX];
long long sp[NMAX];
void read(){
cin>>n>>k;
int i;
for(i=1;i<=n;++i){
cin>>v[i];
sp[i]=sp[i-1]+v[i];
}
}
answer get_dp(long long lambda){
answer best={0,0};
int i;
for(i=1;i<=n;++i){
dp[i]={best.sum+sp[i]-lambda,best.cnt+1};
if(dp[i]<dp[i-1])
dp[i]=dp[i-1];
answer best2={dp[i].sum-sp[i],dp[i].cnt};
if(best<best2)
best=best2;
}
return dp[n];
}
long long bin_search(){
/// (]
long long st=-1,dr=300000000000000;
while(dr-st>1){
long long mij=(st+dr)/2;
if(get_dp(mij).cnt<k)
dr=mij;
else
st=mij;
}
return get_dp(dr).sum+dr*k;
}
int main()
{
read();
cout<<bin_search();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |