Cod sursa(job #2954531)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 14 decembrie 2022 18:42:02
Problema Subsir 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
using namespace std;
ifstream F("subsir2.in");
ofstream G("subsir2.out");
int n,i,a[5001],p[5001],l[5001],m,j,r[5001],q[5001];
void A(int k)
{
    int i;
    if(k==m+1) {
        for(i=1;i<=m&&a[p[i]]==r[i];++i);
        if(i<=m&&a[p[i]]<r[i])
            for(i=1;i<=m;q[i]=p[i],r[i]=a[p[i]],++i);
    } else
        for(i=p[k-1]+1;i<=n;++i)
            if(l[i]==l[p[k-1]]+1&&a[i]>a[p[k-1]])
                p[k]=i,A(k+1);

}
int main()
{
    for(F>>n,i=1;i<=n;F>>a[i],l[i]=1,r[i++]=1e6);
    for(i=2;i<=n;++i)
        for(j=1;j<i;++j)
            if(a[i]>a[j]&&l[i]<l[j]+1)
                l[i]=l[j]+1;
    for(i=1;i<=n;m=max(m,l[i]),++i);
    for(i=1;i<=n;++i)
        if(l[i]==1)
            p[1]=i,A(2);
    for(G<<m<<'\n',i=1;i<=m;G<<q[i++]<<' ');
    return 0;
}