#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define f first
#define s second
int n, k, A[300005]; pll dp[300005][2];
pll better(pll a, pll b){
if (a.f == b.f) return (a.s < b.s ? a : b);
return (a.f > b.f ? a : b);
}
bool solve(ll lmb){
dp[0][0] = {0, 0}; dp[0][1] = {-1e18, 0};
for (int i = 1; i <= n; i++){
dp[i][0] = better(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = better({dp[i - 1][0].f + A[i] - lmb, dp[i - 1][1].s + 1},
{dp[i - 1][1].f + A[i], dp[i - 1][1].s});
}
return better(dp[n][0], dp[n][1]).s <= k;
}
int main(){
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> A[i];
ll L = 0, H = 1e18;
while (L < H){
ll M = (L + H) / 2;
solve(M) ? H = M : L = M + 1;
}
solve(L);
pll res = better(dp[n][0], dp[n][1]);
cout<<res.f + L * k<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
13260 KB |
Output is correct |
2 |
Correct |
361 ms |
13588 KB |
Output is correct |
3 |
Correct |
329 ms |
13720 KB |
Output is correct |
4 |
Correct |
344 ms |
13636 KB |
Output is correct |
5 |
Correct |
339 ms |
13564 KB |
Output is correct |
6 |
Correct |
314 ms |
13384 KB |
Output is correct |
7 |
Correct |
315 ms |
13328 KB |
Output is correct |
8 |
Correct |
336 ms |
13516 KB |
Output is correct |
9 |
Correct |
321 ms |
13396 KB |
Output is correct |
10 |
Correct |
339 ms |
13480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
263 ms |
11716 KB |
Output is correct |
2 |
Correct |
298 ms |
11976 KB |
Output is correct |
3 |
Correct |
256 ms |
11700 KB |
Output is correct |
4 |
Correct |
269 ms |
11920 KB |
Output is correct |
5 |
Correct |
324 ms |
13312 KB |
Output is correct |
6 |
Correct |
262 ms |
11688 KB |
Output is correct |
7 |
Correct |
308 ms |
11992 KB |
Output is correct |
8 |
Correct |
314 ms |
13560 KB |
Output is correct |
9 |
Correct |
341 ms |
13304 KB |
Output is correct |
10 |
Correct |
271 ms |
11908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
326 ms |
13764 KB |
Output is correct |
2 |
Correct |
311 ms |
13592 KB |
Output is correct |
3 |
Correct |
338 ms |
13648 KB |
Output is correct |
4 |
Correct |
313 ms |
13724 KB |
Output is correct |
5 |
Correct |
321 ms |
13628 KB |
Output is correct |
6 |
Correct |
317 ms |
13704 KB |
Output is correct |
7 |
Correct |
314 ms |
13852 KB |
Output is correct |
8 |
Correct |
330 ms |
13680 KB |
Output is correct |
9 |
Correct |
339 ms |
13892 KB |
Output is correct |
10 |
Correct |
335 ms |
13848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
13260 KB |
Output is correct |
2 |
Correct |
361 ms |
13588 KB |
Output is correct |
3 |
Correct |
329 ms |
13720 KB |
Output is correct |
4 |
Correct |
344 ms |
13636 KB |
Output is correct |
5 |
Correct |
339 ms |
13564 KB |
Output is correct |
6 |
Correct |
314 ms |
13384 KB |
Output is correct |
7 |
Correct |
315 ms |
13328 KB |
Output is correct |
8 |
Correct |
336 ms |
13516 KB |
Output is correct |
9 |
Correct |
321 ms |
13396 KB |
Output is correct |
10 |
Correct |
339 ms |
13480 KB |
Output is correct |
11 |
Correct |
263 ms |
11716 KB |
Output is correct |
12 |
Correct |
298 ms |
11976 KB |
Output is correct |
13 |
Correct |
256 ms |
11700 KB |
Output is correct |
14 |
Correct |
269 ms |
11920 KB |
Output is correct |
15 |
Correct |
324 ms |
13312 KB |
Output is correct |
16 |
Correct |
262 ms |
11688 KB |
Output is correct |
17 |
Correct |
308 ms |
11992 KB |
Output is correct |
18 |
Correct |
314 ms |
13560 KB |
Output is correct |
19 |
Correct |
341 ms |
13304 KB |
Output is correct |
20 |
Correct |
271 ms |
11908 KB |
Output is correct |
21 |
Correct |
326 ms |
13764 KB |
Output is correct |
22 |
Correct |
311 ms |
13592 KB |
Output is correct |
23 |
Correct |
338 ms |
13648 KB |
Output is correct |
24 |
Correct |
313 ms |
13724 KB |
Output is correct |
25 |
Correct |
321 ms |
13628 KB |
Output is correct |
26 |
Correct |
317 ms |
13704 KB |
Output is correct |
27 |
Correct |
314 ms |
13852 KB |
Output is correct |
28 |
Correct |
330 ms |
13680 KB |
Output is correct |
29 |
Correct |
339 ms |
13892 KB |
Output is correct |
30 |
Correct |
335 ms |
13848 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |