Submission #1222075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222075		nlkn	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	53 ms	4480 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
	long long first;
long long find_lis(const vector<long long> &a) {
	vector<long long> dp={};
	for (long long i : a) {
		if(i>first)continue;
		long long pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin();
		if (pos == dp.size()) {
			// we can have a new, longer increasing subsequence!
			dp.push_back(i);
		} else {
			// oh ok, at least we can make the ending element smaller
			dp[pos] = i;
		}
	}
	return dp.size();
}
int main() {
	long long n,m; cin >> n >> m;
	vector<long long> arr(n+1);
	for(long long i=0; i<n; i++)cin>>arr[i+1];

	arr[0]=0;
	for(long long i=n,j=0; i>=0; i--,j+=m)arr[i]+=j;
	first=arr[0];
	reverse(arr.begin(),arr.end());
	//cout<<first<<endl;
	cout<<n-find_lis(arr)+1;

}

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