Cod sursa(job #2669611)

Utilizator TudorCretuCretu Tudor Andrei TudorCretu Data 7 noiembrie 2020 12:33:09
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n, v[5005], a[5005], b[5005], i, mn, mx, j,lmn,p,vmn;
bool ok[5005];
int main()
{
	f >> n;
	for (i = 1; i <= n; i++)
		f >> v[i];
	a[n] = 1;
	b[n] = 0;
	for (i = n - 1; i >= 1; i--)
	{
		mn = 1000000000;
		lmn = n + 1;
		p = 0;
		for (j = i + 1; j <= n; j++)
			if (v[j] >= v[i])
			{
				if (v[j] < mn)
				{
					mn = v[j];
					if (a[j] < lmn)
					{
						lmn = a[j];
						vmn = v[j];
						p = j;
					}
					else if(a[j]==lmn)
						if (v[j] < vmn)
						{
							vmn = v[j];
							p = j;
						}
				}
				ok[j] = 1;
			}
		if (p)
		{
			a[i] = lmn + 1;
			b[i] = p;
		}
		else
		{
			b[i] = 0;
			a[i] = 1;

		}
	}
	mn = n + 1;
	for (i = 1; i <= n; i++)
		if (!ok[i])
		{
			if (a[i] < mn)
			{
				mn = a[i];
				p = i;
			}
			else if (a[i] == mn && v[i] < v[p]) p = i;
		}
	g << mn << '\n';
	while (p)
	{
		g << p << " ";
		p = b[p];
	}
}