oj.uz

답안 #298727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
298727 2020-09-13T20:59:34 Z AmineTrabelsi Stove (JOI18_stove) C++17
0 / 100
 58 ms 98412 KB 
#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[5005][5005];
ll solve(int index,int left){
	//cout<<index<<" "<<left<<endl;
	if(index >= n-1){return 0;}
	if(dp[index][left]!=-1)return dp[index][left];
	ll res = solve(index+1,left)+(a[index+1]+1)-(a[index]+1);
	if(left > 0)
	res = min(res,solve(index+1,left-1)+1);
	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(n > 5000){cout<<0<<endl;return 0;}
	int x = (a[1]!=(a[0]+1));
	cout<<solve(0,k-1)+x<<'\n';
	return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 98296 KB Output is correct
2 Incorrect 58 ms 98412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 98296 KB Output is correct
2 Incorrect 58 ms 98412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 98296 KB Output is correct
2 Incorrect 58 ms 98412 KB Output isn't correct
3 Halted 0 ms 0 KB -