Cod sursa(job #478613)

Utilizator freak93Adrian Budau freak93 Data 19 august 2010 13:36:19
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>

using namespace std;

const char iname[]="subsir2.in";
const char oname[]="subsir2.out";
const int inf=0x3f3f3f3f;
const int maxn=5005;

ifstream f(iname);
ofstream g(oname);

int n,a[maxn],next[maxn],l[maxn],i,k,j,maxl,w,rez;

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i];
    k=-inf;
    for(i=n;i;--i)
        if(a[i]>k)
            l[i]=1,k=a[i];
    k=inf;
    for(i=1;i<=n;++i)
        if(a[i]<k)
            next[i]=-1,k=a[i];
    for(i=n-1;i;--i)
    {
        k=inf;
        maxl=inf;
        w=0;
        if(l[i]==0)
        {
            for(j=i+1;j<=n;++j)
            {
                if(a[j]<k&&a[j]>=a[i]&&l[j]<=maxl)
                    maxl=l[j],w=j;
                if(a[j]<k&&a[j]>=a[i])
                    k=a[j];
                if(k<=a[i])
                    break;
            }
            l[i]=maxl+1;
        }
        if(next[i]==-1)
        {
            if(rez==0)
                rez=i;
            if(l[i]<l[rez]||(l[i]==l[rez]&&a[i]<a[rez]))
                rez=i;
        }
        next[i]=w;
    }
    g<<l[rez]<<"\n";
    do
    {
        g<<rez<<" ";
    }while((rez=next[rez]));
    g<<"\n";
}