#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
using namespace std;
const int N = 300005;
int n, k; ll a[N]; pair<ll, ll> dp[N][2];
pair<ll, ll> build(ll lambda) {
memset(dp, 0, sizeof(dp));
dp[1][0] = {0, 0};
dp[1][1] = {a[1] - lambda, 1};
for(ll 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].fi + a[i] - lambda, dp[i - 1][0].se + 1), make_pair(dp[i - 1][1].fi + a[i], dp[i - 1][1].se));
}
return max(dp[n][0], dp[n][1]);
}
bool check(ll lambda) {
return build(lambda).se >= k;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
ll lo = 0, hi = 1e18;
while(lo <= hi) {
ll mid = (lo + hi) >> 1;
if(check(mid)) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
--lo;
cout << build(lo).fi + lo*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... |