Cod sursa(job #2078551)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 29 noiembrie 2017 18:37:36
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

int t[5001],v[5001],n,minim,maxim,b[5001];
bool a[5001];

int main()
{
    fin >> n;
    int i,j;
    for(i=1;i<=n;i++)
    fin >> v[i];
    for(int i=n-1;i>=1;i--)
    {
        minim=1000001;
        for(j=i+1;j<=n;j++)
        {
            if(v[i]<=v[j])
            {
                a[j]=1;
                if(v[j]<minim)
                {
                    minim=v[j];
                    if(t[i]==0)
                        t[i]=j;
                    else if(b[j]<=b[t[i]])
                        t[i]=j;
                }
            }
        }
        if(t[i]!=0)
            b[i]=b[t[i]]+1;
    }
    minim=5001;
    for(i=1;i<=n;i++)
    {
        if(a[i]==0)
        {
            if(b[i]<minim or (b[i]==minim and v[i]<v[maxim]))
            {
                maxim=i;
                minim=b[i];
            }
        }
    }
    fout << b[maxim]+1 <<  '\n';
    fout << maxim << ' ';
    while(t[maxim]!=0)
    {
        maxim=t[maxim];
        fout<<maxim<<" ";
    }
    return 0;
}