Submission #735035

#	Time	Username	Problem	Language	Result	Execution time	Memory
735035		MasterTaster	Rabbit Carrot (LMIO19_triusis)	C++14	63 / 100	39 ms	3144 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define MAXN 100010

ll n, m, a[MAXN], dp[MAXN];

int main() {

    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>a[i];

    int lis=0;
    for (ll i=1; i<=n; i++)
    {
        auto it=upper_bound(dp, dp+lis, m*i-a[i]);
        if (lis==0 || ((distance(dp, it))==0)) if (m*i-a[i]<0) { /*cout<<i<<" wtf"<<endl;*/ continue; }
        if (it==dp+lis)
        {
            dp[lis]=m*i-a[i];
            lis++;
            //cout<<i<<" "<<lis<<endl;
        }
        else
        {
            int j=distance(dp, it);
            dp[j]=m*i-a[i];
        }
        //for (int i=0; i<lis; i++) cout<<dp[i]<<" ";
        //cout<<endl;
    }
    cout<<n-lis;
}

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