#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=-1e14, r=1e14; // Adjusted bounds
while(l<r) {
ll mid=(l+r+1)/2;
if(f(mid).ss>=k) {
l=mid;
} else {
r=mid-1;
}
}
cout<<f(l).ff+l*k;
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... |