Submission #298719

#	Time	Username	Problem	Language	Result	Execution time	Memory
298719		AmineTrabelsi	Stove (JOI18_stove)	C++17	0 / 100	156 ms	262148 KiB

stove

#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][2001];
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 > 2000){cout<<0<<endl;return 0;}
	cout<<solve(0,k)<<'\n';
	return 0;
}
/*
k=2
1 2 3 4 6 7
1-----1 2-2  
*/

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50