제출 #1325931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325931		djsksbrbf	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	21 ms	6564 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define pb push_back
const int MOD = 1e9 + 7;
const int MAX = 2e5 + 5;
#define int ll

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   
   int n, m; cin >> n >> m;
   int a[n + 5];
   
   for(int i = 1 ; i  <= n ; i++)cin >> a[i];
   
   vector <int> v;
   for(int i = 1 ; i <= n ; i++){
      if(a[i] <= i*m){
         v.pb(i*m - a[i]);
      }
   }
   
   vector <int> lis;
   
   for(int i = 0 ; i < (int)v.size() ; i++){
      auto it = upper_bound(lis.begin(), lis.end(), v[i]);
      
      if(it == lis.end()){
         lis.pb(v[i]);
      }
      else{
         *it = v[i];
      }
   }
   
   cout << n - (int)lis.size() << endl;
   
   return 0;
}

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