Cod sursa(job #2063451)

Utilizator KemyKoTeo Virghi KemyKo Data 11 noiembrie 2017 11:40:23
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>

using namespace std;

int mn,use[5002],sol,mx=0,nr[5002],ii,lmax,j, n,i,a[10001],l[10001];

ifstream f("subsir2.in");
ofstream g("subsir2.out");

int main()
{
    f>>n;
    a[n+1]=-1000001;
    for(i=1; i<=n; i++)
        f>>a[i];

    for(i=n; i>=1; i--)
    {
        mn=1000001;
        for(j=i+1; j<=n; j++)
            if(a[j]>=a[i]&&a[j]<mn)
            {
                mn=min(mn,a[j]);
                l[i]=min(l[i],l[j]+1);
                if(!l[i]) l[i]=l[j]+1;
            }
        if(l[i]==0) l[i]=1;
    }

    mn=1000001;
    mx=1000001;
    for(i=1; i<=n; i++)
    {
        if(a[i]<mn) mn=a[i],mx=min(mx,l[i]);
    }

    g<<mx<<'\n';
    i=ii;

    ii=0;
    int aa=-1000001;
    int k=mx;
    while(k)
    {
        mx=mn=1000001;

        for(j=ii+1; j<=n; j++)
            if(l[j]==k&&aa<=a[j]&&mn>a[j])
                mn=a[j],ii=j;
            else if(a[j]>=aa&&a[j]<mn)
                mn=a[j];
        g<<ii<<" ";
        k--;
        aa=a[ii];
    }
    return 0;
}