Cod sursa(job #2063148)

Utilizator darisavuSavu Daria darisavu Data 11 noiembrie 2017 09:50:52
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int l[5005],a[5005],n,r[5005],mx;
void solve()
{
    int i,j,m,mn,k;
    for(i=n-1; i>=1; i--)
    {
        m=0;
        mn=1000005;
        for(j=i+1; j<=n; j++)
        {
            if(a[j]>a[i]&&l[j]>m)
            {
                m=l[j];
            }
        }
        l[i]=m+1;
        for(j=i+1; j<=n; j++)
        {
            if(a[j]>a[i]&&l[j]==m&&a[j]<mn)
            {
                mn=a[j];
                k=j;
            }
        }
        if(mn==1000005) r[i]=i;
        else r[i]=k;
    }
}
int main()
{
    int i,p,mn,k;
    f>>n;
    for(i=1; i<=n; i++) f>>a[i];
    l[n]=1;
    solve();
    mn=1000005;
    for(i=1; i<=n; i++)
    {
        if(l[i]>mx) mx=l[i];

    }
    for(i=1; i<=n; i++)
    {
        if(l[i]==mx)
        {
            if(a[i]<mn)
            {
                mn=a[i];
                p=i;
            }
        }
    }
    g<<mx<<'\n';
    k=1;
    g<<p<<" ";
    while(k<mx)
    {
        p=r[p];
        g<<p<<" ";
        k++;
    }
    return 0;
}