제출 #939113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
939113		ezzzay	Stove (JOI18_stove)	C++14	50 / 100	61 ms	94296 KiB

stove

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=5e3+5;
int arr[N];
int dp[N][N];
signed main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=0;i<=k;i++){
        for(int j=0;j<=n;j++){
            dp[i][j]=INT_MAX;
        }
    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int l=1;l<=k;l++){
            
            dp[l][i]=min(dp[l-1][i-1]+1,dp[l][i-1]+arr[i]-arr[i-1]);
            
        }
    }
    int ans=INT_MAX;
    for(int i=1;i<=k;i++)ans=min(ans,dp[i][n]);
    cout<<ans;
}

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