Cod sursa(job #2291208)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 27 noiembrie 2018 19:14:34
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f ("subsir2.in");
ofstream g ("subsir2.out");
const int nmax=5e3+3;
int n,sol[nmax],nt[nmax],v[nmax],usu,p,s;
int main()
{
	f>>n;
	for(int i=1;i<=n;++i) f>>v[i];
	for(int i=n;i>=1;--i)
	{
		usu=2e9;
		s=usu;
		for(int j=i+1;j<=n;++j)
        {
            if((v[j]>=v[i])&&(v[j]<usu))
            {
					usu=v[j];
					if(sol[j]<=s)
                    {
                        s=sol[j];
                        p=j;
                    }
			}
        }
		if(usu==2e9) sol[i]=1;
		else
        {
            sol[i]=sol[p]+1;
            nt[i]=p;
        }
	}
	usu=sol[1];
	p=1;
	int t=v[1];
	for(int i=2;i<=n;++i)
    {
        if(v[i]<t)
		{
			t=v[i];
			if(sol[i]<=usu)
            {
                usu=sol[i];
                p=i;
            }
		}
    }
	g<<usu<<'\n'<<p<<' ';
	while(--usu)
	{
	    p=nt[p];
	    g<<p<<' ';
    }
	return 0;
}