Submission #1321090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321090		inifnite	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	26 ms	3516 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<ll>
#define pb push_back
#define ii pair<ll,ll>
#define f first
#define s second

const ll INF=1e18;

void solve() {
    ll n,m; cin>>n>>m;
    ll a[n+1]={0};
    for(int i=0; i<n; i++) {
        ll x; cin>>x;
        a[i+1]=x-(i+1)*m;
    }

    vi dp(n+2, INF);
    dp[0]=-INF;

    reverse(a,a+n+1);
    
    int cnt=0;
    for(int i=0; i<n+1; i++) {
        auto it=upper_bound(dp.begin(), dp.end(), a[i])-dp.begin();
        if(dp[it-1]<=a[i] && a[i]<=dp[it]) dp[it]=a[i];
        if(i==n) cnt=it;
    }

    // for(auto i:a) cout<<i<<" ";
    //     cout<<"\n";
    // for(auto i:dp) cout<<i<<" ";
    //     cout<<"\n";

    // cout<<cnt-1<<"\n";
    cout<<(n+1-cnt)<<"\n";
}
 
int main() {
    // #ifndef ONLINE_JUDGE
    // freopen("cowrun.in","r",stdin);
    // freopen("cowrun.out","w",stdout);
    // #endif
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int t = 1;
    while (t--) solve();
    return 0;
}

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