Submission #528447

#	Time	Username	Problem	Language	Result	Execution time	Memory
528447		erto	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	29 ms	6468 KiB

triusis

#include <bits/stdc++.h>
typedef long long int ll;
#define INF ll(1e9 + 7)
#define N (ll)1e5 + 5
using namespace std;



void solve(){
	ll n, m, g, t, t2;
	cin >> n >> m;
	ll a[n], b[n+1];
	for(int i=0 ;i<n; i++){
		cin >> a[i];
		b[i] = m*(i+1) - a[i];
	}
	vector<int> d;
	for(int i=0; i<n; i++){
		if(b[i] < 0)continue;
		g = upper_bound(d.begin(), d.end(), b[i]) - d.begin();
		if(g == d.size()){
			d.push_back(b[i]);
		}
		else{
			d[g] = b[i];
		}
	}
	cout<<n - d.size();


}
 
int main(){
	
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    while (T--){
        solve();
    }
}

Compilation message (stderr)

triusis.cpp: In function 'void solve()':
triusis.cpp:21:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   if(g == d.size()){
      |      ~~^~~~~~~~~~~
triusis.cpp:10:14: warning: unused variable 't' [-Wunused-variable]
   10 |  ll n, m, g, t, t2;
      |              ^
triusis.cpp:10:17: warning: unused variable 't2' [-Wunused-variable]
   10 |  ll n, m, g, t, t2;
      |                 ^~

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