#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)x.size())
const ll maxint=2e18;
const ll minint =-2e18;
/*******\
(͡ ° ͜ʖ ͡ °): Hi, relax.
\* */
const ll M = 1e5+5;
ll n,a[M];
int dp[100000][501];
ll solve(int index,int left){
if(index >= n-1){return 0;}
// keep same match
if(dp[index][left]!=-1)return dp[index][left];
ll res = solve(index+1,left)+a[index+1]-(a[index]);
if(left > 0)
res = min(res,solve(index+1,left-1))+2;
return dp[index][left] = res;
}
int main(){
memset(dp,-1,sizeof(dp));
int k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
if(k > 500){cout<<0<<endl;return 0;}
cout<<solve(0,k)<<'\n';
return 0;
}
/*
k=2
1 2 3 4 6 7
1-----1 2-2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
196344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
196344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
196344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
