#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int n, k;
cin >> n >> k;
int a[n];
for (int &i : a) cin >> i;
auto solveLambda = [&](ll lmb){
pair<ll, ll> dp[n][2];
dp[0][0] = {0, 0};
dp[0][1] = {a[0] - lmb, 0};
for (int i = 1; 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] - lmb, dp[i - 1][0].second + 1),
make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second)
);
}
return max(dp[n - 1][0], dp[n - 1][1]);
};
ll lo = 0, hi = 1e18;
while (lo < hi){
ll mid = (lo + hi) / 2;
solveLambda(mid).second <= k ? hi = mid : lo = mid + 1;
}
cout << solveLambda(lo).first + lo * k << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
151 ms |
13436 KB |
Output is correct |
2 |
Correct |
164 ms |
13684 KB |
Output is correct |
3 |
Correct |
150 ms |
13648 KB |
Output is correct |
4 |
Correct |
149 ms |
13652 KB |
Output is correct |
5 |
Correct |
148 ms |
13652 KB |
Output is correct |
6 |
Correct |
147 ms |
13444 KB |
Output is correct |
7 |
Correct |
149 ms |
13432 KB |
Output is correct |
8 |
Correct |
150 ms |
13720 KB |
Output is correct |
9 |
Correct |
171 ms |
13308 KB |
Output is correct |
10 |
Correct |
149 ms |
13576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
108 ms |
11828 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
184 ms |
13840 KB |
Output is correct |
2 |
Correct |
174 ms |
13648 KB |
Output is correct |
3 |
Correct |
174 ms |
13652 KB |
Output is correct |
4 |
Correct |
175 ms |
13700 KB |
Output is correct |
5 |
Correct |
174 ms |
13648 KB |
Output is correct |
6 |
Correct |
173 ms |
13904 KB |
Output is correct |
7 |
Correct |
181 ms |
13988 KB |
Output is correct |
8 |
Correct |
176 ms |
13652 KB |
Output is correct |
9 |
Correct |
174 ms |
13904 KB |
Output is correct |
10 |
Correct |
176 ms |
13832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
151 ms |
13436 KB |
Output is correct |
2 |
Correct |
164 ms |
13684 KB |
Output is correct |
3 |
Correct |
150 ms |
13648 KB |
Output is correct |
4 |
Correct |
149 ms |
13652 KB |
Output is correct |
5 |
Correct |
148 ms |
13652 KB |
Output is correct |
6 |
Correct |
147 ms |
13444 KB |
Output is correct |
7 |
Correct |
149 ms |
13432 KB |
Output is correct |
8 |
Correct |
150 ms |
13720 KB |
Output is correct |
9 |
Correct |
171 ms |
13308 KB |
Output is correct |
10 |
Correct |
149 ms |
13576 KB |
Output is correct |
11 |
Incorrect |
108 ms |
11828 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |