#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MaxN = 3e5 + 7;
int a[MaxN], n, k;
pair<int, int> dp[MaxN][3];
pair<int, int> calc(int x) {
dp[1][0] = {0, 0};
dp[1][1] = {a[1] - x, 1};
for (int i = 2; 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].first + a[i] - x, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
}
return max(dp[n][0], dp[n][1]);
}
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int l = 0, r = 1e18;
while (l < r) {
int mid = (l + r + 1) / 2;
if (calc(mid).second >= k) {
l = mid;
} else {
r = mid - 1;
}
}
cout << calc(l).first + l * k;
}
# | 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... |