Submission #1020377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020377		ef10	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	61 ms	6968 KiB

triusis

// Source: https://usaco.guide/general/io

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

#define LL long long

LL N, M;
LL A[200005];
LL B[200005];
LL dp[200005];

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		B[i] = M*i-A[i];
	}
	int E = 1;
	for (int i = 1; i <= N; i++) {
		if (B[i] < 0) continue;
		int ind = upper_bound(dp+1,dp+E,B[i])-dp;
		if (ind == E) {
			dp[ind] = B[i];
			E++;
			continue;
		}
		dp[ind] = B[i];
	}
	cout << N-(E-1) << endl;
}

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