제출 #977426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977426		mika_uwu	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	21 ms	4304 KiB

triusis

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define popb pop_back
#define all(A) A.begin(),A.end()
#define rall(A) A.rbegin(),A.rend()
#define dic unordered_map
#define bpc __builtin_popcountll//numero de bits para long long
#define bclz __builtin_clzll//leading zeros para ll
#define max_bit(A) 31-__builtin_clz(A)

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i],a[i]=(i+1)*m-a[i];
    //for(int i=0;i<n;i++) cout<<a[i]<<" ";
    //cout<<"\n";
    vector<int> lis;
    for(int i=0;i<n;i++){
        if(a[i]>=0){
            if(lis.size()==0 || lis.back()<=a[i]) lis.pb(a[i]);
            else{
                int pos=upper_bound(all(lis),a[i])-lis.begin();
                lis[pos]=a[i];
            }
        }
    }
    cout<<n-lis.size()<<"\n";
    return 0;
    // you should actually read the stuff at the bottom
}

/* stuff you should look for
    * int overflow, array bounds
    * bitwise and boolean operations
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

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