Submission #1025896

---

Source Code Expand

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
int main(void) {
    int N;
    cin >> N;
    vector<int>c(N);
    REP(i, N) cin >> c[i];
    vector<int> dp(N+1, 1e9);
    dp[0] = -1e9;
    REP(i, N) {
        int k = c[i];
        int l = 0, r = N+1;
        while(l < r) {
            int m = (l + r) / 2;
            if(k < dp[m]) r = m;
            else l = m+1;
        }
        dp[l] = k;
    }
    int ans = 0;
    REP(i, N+1) {
        if(dp[i] != 1e9) ans = i;
    }
    cout << N-ans << endl;
}

Submission Info

Judge Result