Cod sursa(job #950456)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 16 mai 2013 21:26:10
Problema Subsir 2 Scor 61
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
using namespace std;
ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");

int s[5001],l,v[5002],n,i,ls,ld,m,ind[5001],j,succ[5001],current,ok;

int main ()
{
    fin>>n;
    for (i=1;i<=n;i++) fin>>v[i];
    succ[n]=0;
    for (i=n-1;i>=1;i--)
    {
        ok=0;
        for (j=i+1;j<=n;j++)
        {
            if (ok==0&&v[i]<=v[j]) {ok=1; current=j;}
            if (ok==1&&v[i]<=v[j]&&v[j]<v[current]&&succ[j]<=succ[current]) current=j;
        }
        succ[i]=succ[current]+1;
    }
    s[1]=v[1]; l=1; ind[1]=1;
    for (i=2;i<=n;i++)
    {
      if (v[i]>=s[l]) {s[++l]=v[i]; ind[l]=i; continue;}
      for (j=1;j<=l;j++)
      {
          if (v[i]<s[j]) break;
      }
        if (succ[i]<=succ[ind[j]])
        {
            s[j]=v[i];
            l=j;
            ind[l]=i;
        }
    }
    fout<<l<<"\n";
    for (i=1;i<=l;i++) fout<<ind[i]<<" ";
    return 0;
}