Submission #974452

#	Time	Username	Problem	Language	Result	Execution time	Memory
974452		pete555	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	25 ms	5460 KiB

triusis

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

#define pi pair<int,int>
#define ll long long
#define pb push_back
#define pf push_front

const int MOD = 1e9+7;

int LNDS(const vector<int>& a){
	vector<int> dp;
	for(int i: a){
		int pos = upper_bound(dp.begin(), dp.end(), i) - dp.begin();
		if(pos == dp.size()) dp.pb(i);
		else dp[pos] = i;
	}
	return dp.size();
}

int main()
{
	cin.tie(0)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	vector<int> k;
	for(int i=1; i<=n; i++){
		if(m*i >= a[i-1]) k.pb(m*i - a[i-1]);
	}
	cout << (n - LNDS(k)) << '\n';
}

Compilation message (stderr)

triusis.cpp: In function 'int LNDS(const std::vector<int>&)':
triusis.cpp:15:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   if(pos == dp.size()) dp.pb(i);
      |      ~~~~^~~~~~~~~~~~

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