Submission #1222072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222072		nlkn	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	2 ms	328 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
	
long long find_lis(const vector<long long> &a) {
	vector<long long> dp;
	for (long long i : a) {
		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; int is=0;cin >> n >> m;
	vector<long long> arr(n+1);
	for(long long i=0; i<n; i++)cin>>arr[i+1];
	if(arr[1]>m){
		arr[1]=m;
		is=1;
	}
	arr[0]=0;
	for(long long i=n,j=0; i>=0; i--,j+=m)arr[i]+=j;
	
	reverse(arr.begin(),arr.end());
	cout<<n-find_lis(arr)+1+is;

}

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