#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5;
const long long maxk = 1e2;
long long a[maxn+1];
long long f[maxn+1][maxk+1];
const long long oo = 1e16;
int main()
{
long long n,k; cin >> n >> k;
for (long long i = 1; i <= n; i++) {cin >> a[i];}
for (long long i = 1; i <= k; i++)
{
if (i == 1) {f[1][i] = a[1];} else {f[1][i] = +oo;}
}
for (long long i = 2; i <= n; i++)
{
for (long long j = 1; j <= k; j++)
{
f[i][j] = +oo;
if (j > i) {continue;}
long long curMax = a[i];
for (long long x = i-1; x >= 1; x--)
{
f[i][j] = min(f[i][j], f[x][j-1] + curMax);
curMax = max(curMax, a[x]);
}
}
}
cout << f[n][k];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |