Submission #1238557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238557		PokemonMaster	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	58 ms	5048 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int inf=9e18;
signed main()
{
    int n,m;
    cin>>n>>m;
    vector <int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector <int> b;
    for(int i=1;i<=n;i++)
    {
        if(a[i]-i*m<=0)b.push_back(i*m-a[i]);
    }
    //reverse(b.begin(),b.end());
    vector <int> d(b.size()+1,inf);
    d[0]=-inf;
    for(int i=0;i<b.size();i++)
    {
        int ind=upper_bound(d.begin(),d.end(),b[i]) - d.begin();
        d[ind]=b[i];
    }
    int cnt=0;
    for(int i=1;i<d.size();i++)
    {
        if(d[i]-inf)cnt++;
    }
    cout<<n-cnt;
}   

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