Submission #1278753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278753		IBory	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	18 ms	2616 KiB

triusis

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll N, M;
	cin >> N >> M;

	int ans = 0;
	vector<ll> LIS;
	LIS.push_back(0);
	for (ll i = 1; i <= N; ++i) {
		ll n;
		cin >> n;
		n -= M * i;
		n *= -1;
		if (n < 0) continue;
		if (LIS.back() <= n) LIS.push_back(n);
		else *upper_bound(LIS.begin(), LIS.end(), n) = n;
	}

	cout << N + 1 - LIS.size();
	return 0;
}

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