Cod sursa(job #1646413)

Utilizator duesakBourceanu Cristian duesak Data 10 martie 2016 16:07:38
Problema Subsir 2 Scor 41
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int poz[100001];
int l[5005];
int v[5005];
int prov[5005];
int n;
int main(){
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    poz[n]=-1;
    l[n]=1;
    int j;
    for(int i=n-1;i>0;i--)
        for(poz[i]=-1,l[i]=1,j=i+1;j<=n;j++)
            if(v[i]<=v[j]){
            prov[j]=1;
            if(l[i]<1+l[j]){
                l[i]=l[j]+1;
                poz[i]=j;
            }
            else if(v[j]<v[poz[i]]&&l[i]==1+l[j]){
                poz[i]=j;
            }
            }
    int maxi=1,maxl=5002;
    for(int i=1;i<=n;i++)
    if(maxl>l[i]&&prov[i]==0){maxl=l[i];maxi=i;}
    fout<<maxl<<'\n';
    do{
        fout<<maxi<<" ";
        maxi=poz[maxi];
    }while(maxi!=-1);
    fout<<'\n';
    fin.close();
    fout.close();
}