#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll a[300005];
pair<ll, ll> dp[300005];
void calc(int n, ll c) {
pair<ll, ll> mx(0, 0);
for (int i = 1; i <= n; ++i) {
dp[i] = max(dp[i - 1], {mx.first + a[i] - c, mx.second - 1});
mx = max(mx, {dp[i].first - a[i], dp[i].second});
}
}
void solve() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] += a[i - 1];
}
ll l = 0, r = 1e15;
while (l < r) {
ll mid = (l + r) / 2;
calc(n, mid);
if (-dp[n].second <= k) r = mid;
else l = mid + 1;
}
calc(n, l);
cout << dp[n].first + l * k << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
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... |