Submission #7095171

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;
const int inf = 1e5; //dp[a]は、長さがaの最長増加部分列のうち、末尾が最小のものの最小値を示す
int main(){
int N; cin >> N; vector<int> dp(N+10,inf);
  vector<int> A(N);
  for(int i = 0; i < N; i++){ cin >> A[i];}
  
  for(int i = 0; i < N; i++){
    int p; cin >> p;
    int itr = lower_bound(dp.begin(),dp.end(),p) - dp.begin();
    //dpは昇順にソート済み && dp中でp以上の最小の整数を表す(問題文より重複なし）
    dp[itr] = p;}
  int res;
  for(int i = N; i >= 0; i++){ if( dp[i] != inf){ res = i; break;}}
  
  cout << N - res - 1 << endl; return 0;}
      

Submission Info

Judge Result