Submission #1183724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183724		rcll	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	93 ms	3716 KiB

triusis

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

int lis(const vector<int> &seq) {
	vector<int> min_endings;
	for (int i:seq) {
		int pos=upper_bound(min_endings.begin(),min_endings.end(),i)-min_endings.begin();
		if (pos==min_endings.size()) {
			min_endings.push_back(i);
		} else {
			min_endings[pos]=i;
		}
	}
	return min_endings.size();
}

int main() {
	int n,m;
	cin >> n >> m;
	vector<int> poles(n);
	for (int p=0; p<n; p++) { 
        cin >> poles[p]; 
    }

	vector<int> poss_unchanged;
	for (int i=1; i<=n; i++) {
		if (i*m>=poles[i-1]) {
			poss_unchanged.push_back(i*m-poles[i-1]);
		}
	}
	cout << n-lis(poss_unchanged);
}

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