Submission #949970

#	Time	Username	Problem	Language	Result	Execution time	Memory
949970		vjudge1	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	26 ms	5188 KiB

triusis

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
using ll = int64_t;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m; cin >> n >> m;
	vector<int> a(n);
	for (int& x : a) cin >> x;

	vector<ll> v; 
	for (ll i = 0, x; i < n; i++) {
		x = 1LL * m * (i + 1) - a[i];  // b[i]
		if (x < 0) continue;
		if (v.empty() or x >= v.back()) v.push_back(x);
		else *lower_bound(v.begin(), v.end(), x + 1) = x;
	}

	cout << n - v.size() << endl;
}

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