Submission #1157167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157167		tegshee	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	20 ms	3400 KiB

triusis

#include<bits/stdc++.h>
#define int long long
#define ss second
#define ff first
#define pb push_back
using namespace std;
const int mxn=2e5+4;
const int inf=1e12;
int n,m;
int a[mxn],dp[mxn];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0; i<n; i++) {
    	cin>>a[i];
    	a[i]=(i+1)*m-a[i];
    }
    dp[0]=-inf;
    for(int i=1; i<=n; i++) {
    	dp[i]=inf;
	}
    for(int i=0; i<n; i++){
    	if(a[i]<0) continue;
    	int j=upper_bound(dp,dp+n+1,a[i])-dp;
		  if(dp[j-1]<=a[i]) dp[j]=min(dp[j],a[i]);
    }
   	int k=0;
   	for(int i=1; i<=n; i++) {
   		if(dp[i]<inf) k=i;
	   }
  	cout<<n-k;
}

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