Submission #1201893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201893		samuelandrianoo_	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	1 ms	1864 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
const ll mod = 1000000007;

void fastio(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

vector <ll> min_num;

ll lis(const vector <ll>& nums){

    for (auto num : nums){
        auto it = upper_bound(min_num.begin(), min_num.end(), num);

        if (it == min_num.end()){
            min_num.pb(num);
        }
        else {
            *it = num;
        }
    }
    return min_num.size();
}

int main(){
   fastio();
   ll n, m, arr[200005], cnt = 0, sec[200005], th[200005];
   cin >> n >> m;
   for (ll i = 1; i <= n; i++){
        cin >> arr[i];
   }

   vector<ll> v;
   for (ll i = 1; i <= n; i++){
    if (i * m >= arr[i]) v.pb(arr[i]);
   }

    ll minus = 0;

   auto it = lower_bound(min_num.begin(), min_num.end(), arr[n - 1]);
   if (it == min_num.end() && arr[n] - arr[n - 1] <= m) minus = 1;
   cout << n - lis(v) - minus << endl;
}

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