#include <bits/stdc++.h>
using namespace std;
/// 17:28
typedef long long ll;
const int Nmax = 3e5 + 5, lim = 1e9;
pair<ll, int> dp[Nmax][2];
int a[Nmax], n, k;
pair<ll,int> best(pair<ll, int> a, pair<ll, int> b)
{
if(a.first == b.first) return a.second < b.second ? a : b;
return a.first > b.first ? a : b;
}
pair<ll, int> operator - (pair<ll, int> a, ll x)
{
return {a.first - x, a.second + 1};
}
pair<ll, int> operator + (pair<ll, int> a, ll x)
{
return {a.first + x, a.second};
}
pair<ll, int> solve(ll cost)
{
int i;
dp[0][0] = dp[0][1] = {0, 0};
for(i=1; i<=n; ++i)
{
dp[i][0] = best(dp[i-1][0], dp[i-1][1] - cost);
dp[i][1] = best(dp[i-1][0], dp[i-1][1]) + a[i];
}
return best(dp[n][0], dp[n][1] - cost);
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
int i;
for(i=1; i<=n; ++i) cin >> a[i];
ll mid, st = 0, dr = (ll) n * lim;
while(st <= dr)
{
mid = (st + dr) / 2;
if(solve(mid).second > k) st = mid + 1;
else dr = mid - 1;
}
cout << solve(st).first + (ll) k * st << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
259 ms |
10616 KB |
Output is correct |
| 2 |
Correct |
260 ms |
10744 KB |
Output is correct |
| 3 |
Correct |
270 ms |
10856 KB |
Output is correct |
| 4 |
Correct |
266 ms |
10868 KB |
Output is correct |
| 5 |
Correct |
262 ms |
10744 KB |
Output is correct |
| 6 |
Correct |
254 ms |
10616 KB |
Output is correct |
| 7 |
Correct |
261 ms |
10616 KB |
Output is correct |
| 8 |
Correct |
264 ms |
10840 KB |
Output is correct |
| 9 |
Correct |
255 ms |
10616 KB |
Output is correct |
| 10 |
Correct |
266 ms |
10744 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
227 ms |
10616 KB |
Output is correct |
| 2 |
Correct |
233 ms |
10872 KB |
Output is correct |
| 3 |
Correct |
231 ms |
10616 KB |
Output is correct |
| 4 |
Correct |
235 ms |
10744 KB |
Output is correct |
| 5 |
Correct |
258 ms |
10616 KB |
Output is correct |
| 6 |
Correct |
248 ms |
10616 KB |
Output is correct |
| 7 |
Correct |
242 ms |
10872 KB |
Output is correct |
| 8 |
Correct |
265 ms |
10872 KB |
Output is correct |
| 9 |
Correct |
269 ms |
10488 KB |
Output is correct |
| 10 |
Correct |
234 ms |
10872 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
255 ms |
10744 KB |
Output is correct |
| 2 |
Correct |
242 ms |
10616 KB |
Output is correct |
| 3 |
Correct |
245 ms |
10740 KB |
Output is correct |
| 4 |
Correct |
242 ms |
10616 KB |
Output is correct |
| 5 |
Correct |
243 ms |
10744 KB |
Output is correct |
| 6 |
Correct |
246 ms |
10848 KB |
Output is correct |
| 7 |
Correct |
248 ms |
10872 KB |
Output is correct |
| 8 |
Correct |
243 ms |
10744 KB |
Output is correct |
| 9 |
Correct |
248 ms |
10872 KB |
Output is correct |
| 10 |
Correct |
247 ms |
10872 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
380 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
4 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
380 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
380 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
4 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
380 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
5 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
376 KB |
Output is correct |
| 16 |
Correct |
6 ms |
376 KB |
Output is correct |
| 17 |
Correct |
5 ms |
376 KB |
Output is correct |
| 18 |
Correct |
5 ms |
376 KB |
Output is correct |
| 19 |
Correct |
5 ms |
376 KB |
Output is correct |
| 20 |
Correct |
5 ms |
380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
380 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
4 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
380 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
5 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
376 KB |
Output is correct |
| 16 |
Correct |
6 ms |
376 KB |
Output is correct |
| 17 |
Correct |
5 ms |
376 KB |
Output is correct |
| 18 |
Correct |
5 ms |
376 KB |
Output is correct |
| 19 |
Correct |
5 ms |
376 KB |
Output is correct |
| 20 |
Correct |
5 ms |
380 KB |
Output is correct |
| 21 |
Correct |
6 ms |
376 KB |
Output is correct |
| 22 |
Correct |
7 ms |
376 KB |
Output is correct |
| 23 |
Correct |
6 ms |
376 KB |
Output is correct |
| 24 |
Correct |
6 ms |
248 KB |
Output is correct |
| 25 |
Correct |
6 ms |
376 KB |
Output is correct |
| 26 |
Correct |
6 ms |
376 KB |
Output is correct |
| 27 |
Correct |
6 ms |
376 KB |
Output is correct |
| 28 |
Correct |
6 ms |
376 KB |
Output is correct |
| 29 |
Correct |
6 ms |
376 KB |
Output is correct |
| 30 |
Correct |
6 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
259 ms |
10616 KB |
Output is correct |
| 2 |
Correct |
260 ms |
10744 KB |
Output is correct |
| 3 |
Correct |
270 ms |
10856 KB |
Output is correct |
| 4 |
Correct |
266 ms |
10868 KB |
Output is correct |
| 5 |
Correct |
262 ms |
10744 KB |
Output is correct |
| 6 |
Correct |
254 ms |
10616 KB |
Output is correct |
| 7 |
Correct |
261 ms |
10616 KB |
Output is correct |
| 8 |
Correct |
264 ms |
10840 KB |
Output is correct |
| 9 |
Correct |
255 ms |
10616 KB |
Output is correct |
| 10 |
Correct |
266 ms |
10744 KB |
Output is correct |
| 11 |
Correct |
227 ms |
10616 KB |
Output is correct |
| 12 |
Correct |
233 ms |
10872 KB |
Output is correct |
| 13 |
Correct |
231 ms |
10616 KB |
Output is correct |
| 14 |
Correct |
235 ms |
10744 KB |
Output is correct |
| 15 |
Correct |
258 ms |
10616 KB |
Output is correct |
| 16 |
Correct |
248 ms |
10616 KB |
Output is correct |
| 17 |
Correct |
242 ms |
10872 KB |
Output is correct |
| 18 |
Correct |
265 ms |
10872 KB |
Output is correct |
| 19 |
Correct |
269 ms |
10488 KB |
Output is correct |
| 20 |
Correct |
234 ms |
10872 KB |
Output is correct |
| 21 |
Correct |
255 ms |
10744 KB |
Output is correct |
| 22 |
Correct |
242 ms |
10616 KB |
Output is correct |
| 23 |
Correct |
245 ms |
10740 KB |
Output is correct |
| 24 |
Correct |
242 ms |
10616 KB |
Output is correct |
| 25 |
Correct |
243 ms |
10744 KB |
Output is correct |
| 26 |
Correct |
246 ms |
10848 KB |
Output is correct |
| 27 |
Correct |
248 ms |
10872 KB |
Output is correct |
| 28 |
Correct |
243 ms |
10744 KB |
Output is correct |
| 29 |
Correct |
248 ms |
10872 KB |
Output is correct |
| 30 |
Correct |
247 ms |
10872 KB |
Output is correct |
| 31 |
Correct |
5 ms |
376 KB |
Output is correct |
| 32 |
Correct |
5 ms |
376 KB |
Output is correct |
| 33 |
Correct |
5 ms |
380 KB |
Output is correct |
| 34 |
Correct |
5 ms |
376 KB |
Output is correct |
| 35 |
Correct |
5 ms |
376 KB |
Output is correct |
| 36 |
Correct |
4 ms |
376 KB |
Output is correct |
| 37 |
Correct |
5 ms |
380 KB |
Output is correct |
| 38 |
Correct |
5 ms |
376 KB |
Output is correct |
| 39 |
Correct |
5 ms |
376 KB |
Output is correct |
| 40 |
Correct |
5 ms |
376 KB |
Output is correct |
| 41 |
Correct |
5 ms |
376 KB |
Output is correct |
| 42 |
Correct |
5 ms |
376 KB |
Output is correct |
| 43 |
Correct |
5 ms |
376 KB |
Output is correct |
| 44 |
Correct |
5 ms |
376 KB |
Output is correct |
| 45 |
Correct |
5 ms |
376 KB |
Output is correct |
| 46 |
Correct |
6 ms |
376 KB |
Output is correct |
| 47 |
Correct |
5 ms |
376 KB |
Output is correct |
| 48 |
Correct |
5 ms |
376 KB |
Output is correct |
| 49 |
Correct |
5 ms |
376 KB |
Output is correct |
| 50 |
Correct |
5 ms |
380 KB |
Output is correct |
| 51 |
Correct |
6 ms |
376 KB |
Output is correct |
| 52 |
Correct |
7 ms |
376 KB |
Output is correct |
| 53 |
Correct |
6 ms |
376 KB |
Output is correct |
| 54 |
Correct |
6 ms |
248 KB |
Output is correct |
| 55 |
Correct |
6 ms |
376 KB |
Output is correct |
| 56 |
Correct |
6 ms |
376 KB |
Output is correct |
| 57 |
Correct |
6 ms |
376 KB |
Output is correct |
| 58 |
Correct |
6 ms |
376 KB |
Output is correct |
| 59 |
Correct |
6 ms |
376 KB |
Output is correct |
| 60 |
Correct |
6 ms |
376 KB |
Output is correct |
| 61 |
Correct |
284 ms |
10616 KB |
Output is correct |
| 62 |
Correct |
307 ms |
10872 KB |
Output is correct |
| 63 |
Correct |
247 ms |
10616 KB |
Output is correct |
| 64 |
Correct |
283 ms |
10872 KB |
Output is correct |
| 65 |
Correct |
285 ms |
10872 KB |
Output is correct |
| 66 |
Correct |
272 ms |
10744 KB |
Output is correct |
| 67 |
Correct |
274 ms |
10620 KB |
Output is correct |
| 68 |
Correct |
246 ms |
10876 KB |
Output is correct |
| 69 |
Correct |
242 ms |
10616 KB |
Output is correct |
| 70 |
Correct |
237 ms |
10488 KB |
Output is correct |
