Submission #639633

#	Time	Username	Problem	Language	Result	Execution time	Memory
639633		Sofiatpc	Rabbit Carrot (LMIO19_triusis)	C++14	0 / 100	1 ms	212 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

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

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

    int s = h[i];
    if(a==1)h[i]=h[i-1]+M;

    dp[i][a]=fazdp(i+1,1)+1;
    if(h[i+1] <= h[i]+M )dp[i][a]=min(dp[i][a],fazdp(i+1,0));

    h[i]=s;
    return dp[i][a];
}

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

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

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

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

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