Submission #730220

#	Time	Username	Problem	Language	Result	Execution time	Memory
730220		dubabuba	Rabbit Carrot (LMIO19_triusis)	C++14	0 / 100	1 ms	232 KiB

triusis

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

typedef pair<int, int> pii;
#define ff first
#define ss second

int n, m, t;
vector<int> a;
vector<pii> b;

int LIS() {
	vector<int> dp;
	sort(b.begin(), b.end());

	for(pii x : b) {
		int id = lower_bound(dp.begin(), dp.end(), x.ss) - dp.begin();
		if(id == (int)dp.size()) dp.push_back(x.ss);
		else dp[id] = x.ss;
	}
	return dp.size();
}

int main() {
	cin >> n >> m;
	
	a.push_back(0);
	for(int i = 1; i <= n; i++) {
		a.push_back(0);
		cin >> a[i];

		if(a[i] <= m * i) {
			b.push_back({m * i - a[i], m * i + a[i]});
			// cout << a[i] << ": " << m * i - a[i] << ' ' << m * i + a[i] << '\n';
		}
	}

	cout << n - LIS() << '\n';
	return 0;
}

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