Submission #155247

---

Source Code Expand

#include <iostream>
#include <algorithm>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)

const int N_MAX = (int)(3*1e4);
const int INF = (int)(1e6);

int N;
int c[N_MAX];

int dp[N_MAX];

void solve()
{
    REP(i, N+1) dp[i] = INF;
    REP(i, N) *lower_bound(dp, dp+N, c[i]) = c[i];
    int ans = N-(lower_bound(dp, dp+N, INF)-dp);
    cout << ans << endl;
}

int main()
{
    cin >> N;
    REP(i, N) cin >> c[i];
    solve();
    return 0;
}

Submission Info

Judge Result