#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 3e5+3;
int n, k; ll a[N];
pair<ll, int> dp[N][2];
pair<ll, int> calc(ll lam){
dp[1][1] = make_pair(a[1] - lam, 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] - lam, 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]);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
int mxc = 0;
for(int i = 1; i <= n; i++)
if(a[i] >= 0) mxc++;
k = min(k, mxc);
ll L = 0, R = 1e18+1;
while(L <= R){
ll mid = (L+R)/2;
if(calc(mid).second >= k) L = mid + 1;
else R = mid - 1;
}
// cout << L << " ";
L--;
cout << calc(L).first + k * L;
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... |