Submission #1305939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305939		Nipphitch	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	20 ms	6592 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e5+5;

int n,m,a[N];
vector <int> vec,dp;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) if(a[i]<=i*m) vec.push_back(i*m-a[i]);
    for(int x:vec){
        int idx=upper_bound(dp.begin(),dp.end(),x)-dp.begin();
        if(idx==dp.size()) dp.push_back(x);
        else dp[idx]=x;
    }
    cout << n-dp.size();
}

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