Submission #170609

#	Time	Username	Problem	Language	Result	Execution time	Memory
170609		mdn2002	Stove (JOI18_stove)	C++14	20 / 100	1088 ms	200140 KiB

stove

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,k,a[5050],dp[5050][5050];
long long f(int x,int ma)
{
    if(ma>k)return 1e9+2;
    if(x==n)return 0;
    if(dp[x][ma]!=-1)return dp[x][ma];
    long long num=1e9+2;
    for(int i=x;i<n;i++)
    {
        num=min(num,f(i+1,ma+1)+a[i]-a[x]+1);
    }
    return dp[x][ma]=num;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp,-1,sizeof dp);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    cout<<f(0,0);
}

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