Cod sursa(job #2241293)

Utilizator TheNextGenerationAyy LMAO TheNextGeneration Data 15 septembrie 2018 14:48:17
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("euro2.in");
ofstream out("euro2.out");
const int NMAX = 10005;

int v[NMAX],nrm[NMAX],dp1[NMAX],dp2[NMAX],fn[NMAX],n;
int query(int x)
{
    int Max = 0;
    while (x>0)
    {
        if (fn[x]>Max)
            Max = fn[x];
        x-=x&-x;
    }
    return Max;
}

void update(int val, int x)
{
    while (x<=n)
    {
        if (val>fn[x])
            fn[x] = val;
        x+=x&-x;
    }
}

int main()
{
    in >> n;
    for (int i = 1; i<=n; i++)
    {
        int x = 0;
        string s;
        in >> s;
        for (auto it: s)
            if (it!='.')
                x = x*10+it-'0';
        v[i] = nrm[i] = x;
    }
    sort(nrm+1,nrm+n+1);
    int h = 1;
    for (int i = 2; i<=n; i++)
        if (nrm[i]!=nrm[i-1])
            nrm[++h] = nrm[i];
    for (int i = 1; i<=n; i++)
        v[i] = lower_bound(nrm+1,nrm+n+1,v[i])-nrm;
    for (int i = 1; i<=n; i++)
    {
        dp1[i] = query(v[i]-1)+1;
        update(dp1[i],v[i]);
    }
    reverse(v+1,v+n+1);
    memset(fn,0,sizeof(fn));
    for (int i = 1; i<=n; i++)
    {
        dp2[i] = query(v[i]-1)+1;
        update(dp2[i],v[i]);
    }
    int Max = 0;
    for (int i = 1; i<=n; i++)
        if (dp1[i]>=2 && dp2[i]>=2)
        Max = max(Max,dp1[i]+dp2[n-i+1]-1);
    out << Max;
}