Submission #639653

#	Time	Username	Problem	Language	Result	Execution time	Memory
639653		Sofiatpc	Rabbit Carrot (LMIO19_triusis)	C++14	14 / 100	196 ms	98492 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

const int MAXN =  5005;
int N,M, dp[MAXN][MAXN], h[MAXN];

int fazdp(int i, int cur)
{
    if(i==N)return dp[i][cur]=0;
    if(dp[i][cur]!=-1)return dp[i][cur];

    dp[i][cur]=fazdp(i+1,cur+M)+1;
    if(h[i+1] <= cur+M )dp[i][cur]=min(dp[i][cur],fazdp(i+1,h[i+1]));
    return dp[i][cur];
}

int main()
{
    cin>>N>>M;
    for(int i = 1; i <= N; i++)cin>>h[i];

    for(int i = 1; i <= N; i++)
        for(int cur = 0; cur <= 5000; cur++)dp[i][cur]=-1;

    h[0]=0;
    int ans = fazdp(1,M)+1;
    if(h[1]<=h[0]+M)ans=min(fazdp(1,h[1]),ans);


    cout<<ans<<"\n";
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37