Submission #1177842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177842		mathlatex123	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	60 ms	3512 KiB

triusis

//
//  main.cpp
//  XCAMP_WEEK10_PROBLEM3
//
//  Created by Ishaan Mittal on 4/1/25.
//

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

int main() {
    ll n,m;
    cin>>n>>m;
    vector<ll> arr;
    ll temp;
    for(ll i=1;i<=n;i++){
        cin>>temp;
        temp-=i*m;
        if(temp<=0) arr.push_back(temp);
    }
    reverse(arr.begin(),arr.end());
    vector<ll> dp(arr.size()+1,1e9);
    dp[0]=-1e9;
    for(ll i=0;i<arr.size();i++){
        ll l=upper_bound(dp.begin(),dp.end(),arr[i])-dp.begin();
        if(dp[l-1]<=arr[i]&&arr[i]<=dp[l])dp[l]=arr[i];
    }
    ll ans=0;
    for(ll l=0;l<=arr.size();l++) {
        if(dp[l]<1e9)
            ans=l;
    }
    cout<<n-ans;
}

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