Submission #156876

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  int n;
  cin >> n;

  int res = 1;
  vector<int> arr(n);
  vector<int> dp(n + 1);

  for(int i=0;i<n;++i){
	cin >> arr[i];
  }

  dp[0] = 0x80000000;
  fill(dp.begin()+1, dp.end(), 0x7fffffff);

  for(int i=0;i<n;++i){
	vector<int>::iterator lb = lower_bound(dp.begin(), dp.end(), arr[i]);
	*lb = arr[i];
  }

  vector<int>::iterator e = lower_bound(dp.begin(), dp.end(), n+1);
  cout << n - (e - dp.begin()) + 1 << endl;
  return 0;
}

Submission Info

Judge Result