#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
const int mxN=3e5;
ll a[mxN+1];
pair<ll, ll> dp[mxN+1][2];
ll n, k;
pair<ll, ll> f(ll p) {
dp[0][0]={0, 0};
dp[0][1]={a[0]-p, 1};
for(int i=1; i<n; i++) {
dp[i][0]=max(dp[i-1][0], dp[i-1][1]);
dp[i][1]=max(make_pair(dp[i-1][0].ff+a[i]-p, dp[i-1][0].ss+1), make_pair(dp[i-1][1].ff+a[i], dp[i-1][1].ss));
}
return max(dp[n-1][0], dp[n-1][1]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>k;
for(int i=0; i<n; i++) {
cin>>a[i];
}
ll l=-1e9, r=1e18;
while(l<=r) {
ll mid=(l+r)/2;
if(f(mid).ss>k) {
l=mid+1;
} else {
r=mid-1;
}
}
cout<<f(l).ff+l*k;
return 0;
}
//rating below 2400 must be solved orzorzorz
# | 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... |