#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int INF = 1e18 + 5;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
vector<int> a(n);
for(int &x : a) cin >> x;
int lo = -1e9, hi = 1e9, ans = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
auto check = [&](int lb){
vector dp(2, vector<pii> (n, {INF, INF}));
dp[0][0] = {0, 0};
dp[1][0] = {-lb, 1};
for(int i = 1; i < n; i++){
dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
dp[1][i] = max(pii {dp[0][i - 1].first - lb + a[i], dp[0][i - 1].second + 1},
{dp[1][i - 1].first + a[i], dp[0][i - 1].second});
}
return max(dp[0][n - 1], dp[1][n - 1]);
};
pii cur = check(mid);
if(cur.second >= k){
ans = cur.first + mid * k, lo = mid + 1;
} else{
hi = mid - 1;
}
}
cout << ans << '\n';
}
# | 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... |