Submission #1117332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117332		KALARRY	Rabbit Carrot (LMIO19_triusis)	C++14	63 / 100	1060 ms	1696 KiB

triusis

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int N,M,a[200005],dp[200005];

int main()
{
    scanf("%d%d",&N,&M);
    for(int i = 1 ; i <= N ; i++)
        scanf("%d",&a[i]);
    int ans = N;
    for(int i = 1 ; i <= N ; i++)
    {
        dp[i] = INF;
        for(int j = i-1 ; j >= 0 ; j--) //last not changed is j
        {
            long long max_reach = a[j] + (i - j)*M;
            if(max_reach >= a[i])
                dp[i] = min(dp[i],dp[j] + (i-1-j));
        }
        ans = min(ans,dp[i] + N-i);
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d%d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~
triusis.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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