Submission #1164789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164789		UmairAhmadMirza	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	1 ms	584 KiB

triusis

#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=2e5+5;
int const mod=1e9+7;

int arr[N];

int LDS(vector<int> v){
	reverse(v.begin(), v.end());
	// for(int i:v)
	// 	cout<<i<<' ';
	// cout<<endl;
	int n=v.size();
	vector<int> lis;
	for(int i=0;i<n;i++){
		auto p=upper_bound(lis.begin(), lis.end(),v[i]);
		if(p==lis.end()){
			// cout<<v[i]<<-1<<endl;
			lis.push_back(v[i]);
		}
		else{
			// cout<<v[i]<<' '<<p-lis.begin()<<endl;
			lis[p-lis.begin()]=v[i];
		}
	}
	// cout<<lis.size()<<endl;
	return (lis.size());
}

void solve(){
	int n,m;
	cin>>n>>m;
	arr[0]=0;
	vector<int> v;
	for (int i = 1; i <=n; ++i){
		cin>>arr[i];
		arr[i]-=m*i;
		if(arr[i]<0)
			v.push_back(arr[i]);
	}
	cout<<n-LDS(v)<<endl;
}

signed main(){
	int t=1;
	// cin>>t;
	while(t--)
		solve();
	return 0;
}

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