#include <bits/stdc++.h>
#define mp make_pair
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int mod=1e9 + 7;
const int maxN=5e5+7;
int n,k,a[maxN];
pii dp[2][maxN];
pii sol(int lmb)
{
dp[0][0]={0,0};
dp[1][0]={-lmb,1};
for(int i=1; i<=n; i++)
{
dp[0][i]=max(dp[0][i-1],dp[1][i-1]);
dp[1][i]=max(mp(dp[0][i-1].fi+a[i]-lmb,dp[0][i-1].se+1),mp(dp[1][i-1].fi+a[i],dp[1][i-1].se));
}
return max(dp[0][n],dp[1][n]);
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for(int i=1; i<=n; i++) cin>>a[i];
int l=0,r=1e18,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(sol(mid).se>=k)
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<sol(ans).fi+ans*k<<endl;
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... |