#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 3e5+5;
int n,k,a[N];
pii dp[N][2];
pii check(int mid){
dp[1][0] = {0,0};
dp[1][1] = {a[1]-mid,1};
for(int i = 2; i <= n; i++){
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
pii c1 = {dp[i-1][0].fi+a[i]-mid,dp[i-1][0].se+1};
pii c2 = {dp[i-1][1].fi+a[i],dp[i-1][1].se};
dp[i][1] = max(c1,c2);
}
return max(dp[n][0],dp[n][1]);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
int l = 0;
int r = 1e14;
while(l <= r){
int mid = (l+r)/2;
if(check(mid).se > k) l = mid+1;
else r = mid-1;
}
cout << check(l).fi+k*l;
}
# | 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... |