Submission #1279822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279822		cmiuc	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	25 ms	2004 KiB

triusis

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;
int dp[N], a[N], n, M, Ans;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n>>M;

	for (int i=1, b;i<=n;i++){
		cin>>b;
		a[n - i + 1] = b - i * M;
	}

	for (int i=1;i<=n;i++)
		dp[i] = 2e9;
	dp[0] = -dp[1];

	for (int i=1;i<=n;i++){
		int u = upper_bound(dp, dp + n + 1, a[i]) - dp;
		dp[u] = a[i];
		if (a[i] <= 0 and u > Ans)
			Ans = u;
	}
	cout<<n - Ans<<endl;
}

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