Cod sursa(job #723414)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 25 martie 2012 14:29:53
Problema Subsir 2 Scor 22
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
using namespace std;

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

int n,a[5001],sol[5001][5001];

int main()
{
    int i,j=1,jj,k,min1=5001;
    bool good;
    f>>n;
    for(i=1;i<=n;i++) f>>a[i];
    f.close();
    min1=a[1];
    sol[1][0]=1; sol[1][1]=1;
    for(i=2;i<=n;i++)
    {
        int lmin=5001;
        if(a[i]<min1) {sol[i][1]=i; sol[i][0]=1; min1=a[i]; continue;}
        for(j=1;j<i;j++)
        {
            k=sol[j][0];
            if(a[i]<a[sol[j][k]]) continue;
            good=1;
            for(jj=sol[j][k]+1;jj<i;jj++) if(a[i]>a[jj]) {good=0; break;}
            if(good)
            {
                if(lmin>k)
                {
                    for(jj=1;jj<=k;jj++) sol[i][jj]=sol[j][jj];
                    sol[i][0]=k+1;
                    sol[i][k+1]=i;
                    lmin=k;
                }
                else if(lmin==k)
                {
                    good=1;
                    for(jj=1;jj<=k;jj++) if(sol[i][jj]<sol[j][jj]) {good=0; break;}
                    if(good)
                    {
                        for(jj=1;jj<=k;jj++) sol[i][jj]=sol[j][jj];
                        sol[i][0]=k+1;
                        sol[i][k+1]=i;
                        lmin=k;
                    }

                }
            }
        }

    }
    g<<sol[n][0]<<"\n";
    for(i=1;i<=sol[n][0];i++) g<<sol[n][i]<<" ";
    g<<"\n";
    g.close();
    return 0;
}