Submission #1101741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101741		0pt1mus23	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	22 ms	9932 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
#define _ << " " <<
mt19937 rng(time(0));

const int mod = 1e9 +9,
        sze = 5e3 +23,
        inf = INT_MAX,
        LL = 20;


void hiz(){
    int n,m;
    cin>>n>>m;
    vector<int> arr(n+1);
    vector<int> lst;
    for(int i=0;i<n;i++){
        cin>>arr[i+1];
        if(arr[i+1]<=(i+1)*m){
            lst.pb((i+1)*m - arr[i+1]);
        }
    }

    vector<int> lis;
    for(auto v:lst){
        if(lis.empty() || lis.back()<=v){
            lis.pb(v);
        }
        else{
            auto it = upper_bound(all(lis),v);
            *it = v;
        }

    }


    cout<< n - lis.size() <<endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;

    // cin>>tt;
    while(tt--){
        hiz();
    }
 
    return 0;
}

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