제출 #1123404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123404		ardadut	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	26 ms	4032 KiB

triusis

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/


inline void solve(){
    
    ll n,m;
    cin >> n >> m;

    vector<ll> a(n+1);
    vector<ll> lis;

    for(ll i = 1 ; i <= n ; i++){
        ll x;
        cin >> x;
        a[i] = m * i - x;
    }

    lis.pb(0);

    for(ll i = 1 ; i <= n ; i++){
        ll j = upper_bound(lis.begin(),lis.end(),a[i]) - lis.begin();
        if(j == lis.size()) lis.pb(a[i]);
        else if(j != 0) lis[j] = a[i];
    }

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

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

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