Submission #996535

#	Time	Username	Problem	Language	Result	Execution time	Memory
996535		aykhn	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	20 ms	6104 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 3e5 + 5;

void _()
{
	int n, m;
	cin >> n >> m;
	int a[n];
	for (int i = 0; i < n; i++) cin >> a[i], a[i] -= (i + 1) * m;
	vector<int> v;
	for (int i = 0; i < n; i++)
	{
		if (a[i] > 0) continue;
		a[i] = -a[i];
		if (v.empty() || v.back() <= a[i]) v.push_back(a[i]);
		else v[upper_bound(v.begin(), v.end(), a[i]) - v.begin()] = a[i];
	}
	cout << n - (int)v.size() << '\n';
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for (int tt = 1; tt <= t; tt++)
	{
		_();
	}
}

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