Submission #355439

#	Time	Username	Problem	Language	Result	Execution time	Memory
355439		penguinhacker	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	31 ms	4204 KiB

triusis

// source: https://oj.uz/problem/view/LMIO19_triusis
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int n, m, a[200001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	a[0] = 1e9;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i] = 1e9 - (a[i] - i * m);
	}
	vector<int> lis;
	for (int i = 1; i <= n; ++i) {
		if (a[i] >= 1e9) {
			auto it = upper_bound(lis.begin(), lis.end(), a[i]);
			if (it == lis.end()) lis.push_back(a[i]);
			else *it = a[i];
		}
	}
	cout << n - lis.size();
	return 0;
}

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