Submission #1117338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117338		KALARRY	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	26 ms	5256 KiB

triusis

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const long long INF = 1e18;

long long N,M,a[200005],b[200005],dp[200005];

int main()
{
    scanf("%lld%lld",&N,&M);
    for(long long i = 1 ; i <= N ; i++)
    {
        scanf("%lld",&a[i]);
        b[i] = M*i - a[i];
    }
    dp[0] = 0;
    for(long long i = 1 ; i <= N ; i++)
        dp[i] = INF;
    long long ans = 0;
    for(long long i = 1 ; i <= N ; i++)
    {
        if(b[i] < 0)
            continue;
        long long pos = upper_bound(dp,dp+N+1,b[i]) - dp - 1;
        dp[pos+1] = min(dp[pos+1],b[i]);
        ans = max(ans,pos+1);
    }
    printf("%lld\n",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("%lld%lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
triusis.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~

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