Cod sursa(job #2958517)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 26 decembrie 2022 20:30:13
Problema Subsir 2 Scor 63
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<fstream>
using namespace std;
ifstream F("subsir2.in");
ofstream G("subsir2.out");
int n,i,a[5001],l[5001],p[5001],m,j,k,t;
int main()
{
    for(F>>n,i=1;i<=n;F>>a[i++]);
    for(l[n]=1,p[n]=n,i=n-1;i;l[i]=l[i]==n?1:l[i],--i)
        for(m=1e6,l[i]=n,p[i]=i,j=i+1;j<=n;++j)
            if(a[j]>=a[i]&&a[j]<=m)
                if(m=a[j],l[i]>=l[j]+1)
                    l[i]=l[j]+1,p[i]=j;
    //for(i=1;i<=n;G<<i<<' '<<a[i]<<' '<<l[i]<<' '<<p[i]<<'\n',++i);
    /*for(t=1,i=2;i<=n&&l[i]<=l[t];++i)
        if(l[i]==l[t])
            if(a[i]<a[t])
                t=i;
            else if(a[i]==a[t]) {
                for(j=i,k=t;a[j]==a[k]&&j!=p[j]&&k!=p[k];j=p[j],k=p[k]);
                if(a[j]<a[k])
                    t=i;
            }
    for(i=t,G<<l[i]<<'\n';i!=p[i];G<<i<<' ',i=p[i]);*/
    for(m=a[1],k=1,i=2;i<=n&&l[i]<=l[k];++i)
        if(a[i]<a[k])
            m=a[i],k=i;
    for(i=k,G<<l[i]<<'\n';i!=p[i];G<<i<<' ',i=p[i]);
    return G<<i,0;
}