#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int N = 3e5 + 17;
int n, k;
long long a[N];
pair <long long, int> f[N][7], m;
inline pair <long long, int> calc (long long c)
{
f[1][0] = {0, 0}, f[1][1] = {a[1] - c, 1};
for (int i = 2; i <= n; ++i)
{
f[i][0] = max (f[i - 1][0], f[i - 1][1]);
f[i][1] = max (make_pair (f[i - 1][1].first + a[i], f[i - 1][1].second),
make_pair (f[i - 1][0].first + a[i] - c, f[i - 1][0].second + 1));
}
return max (f[n][0], f[n][1]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
long long l = 1, r = 3e14;
while (l < r)
{
long long mid = l + r + 1 >> 1;
m = calc (mid);
if (m.second >= k)
{
l = mid;
continue;
}
r = mid - 1;
}
m = calc(l);
long long ans = l * m.second + m.first;
cout << ans;
}
# | 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... |