Submission #1370304

---

Source Code Expand

/*
ID: 5ak0
PROG:
LANG: C++11
*/

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 1e3 + 10;

int n, a[MAXN], b[MAXN], ans[MAXN][MAXN];

int main(){
    #ifndef SAKO
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    #endif // SAKO
    ios_base::sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        b[i] = a[i];
    }
    sort (b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (a[i] == b[j])
                ans[i][j] = ans[i - 1][j - 1] + 1;
            else
                ans[i][j] = max(ans[i][j - 1], ans[i - 1][j]);
    cout << ans[n][n];
    return 0;
}

Submission Info

Judge Result