Cod sursa(job #1511650)

Utilizator ArkinyStoica Alex Arkiny Data 26 octombrie 2015 23:26:43
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <stdlib.h>
#include<vector>

std::vector<int> v[201];
int D[201];
int C[201];
int A[201];
int N, K, i, j, max_i = 1, max, p;
FILE *in, *out;
int st[201], s = 0;
void findNChild(int i,int &nr)
{
	for (j = v[i].size() - 1;j >= 0;--j)
		if (K - C[v[i][j]] > 0)
			K = K - C[v[i][j]];
		else if (C[v[i][j]] == 1)
		{
			fprintf(out, "%d ", i);
			i = v[i][j];
			break;
		}
		else
		{
			fprintf(out, "%d ", i);
			i = v[i][j];
			j = v[i].size();
		}

		while (v[i].size())
		{
			fprintf(out, "%d ", i);
			i = v[i][0];
		}
		fprintf(out, "%d ", i);

}

int main()
{
	in = fopen("cuvinte.in", "r");
	out = fopen("cuvinte.out", "w");

	fscanf(in, "%d%d", &N, &K);
	for (i = 1;i <= N;++i)
		fscanf(in, "%d", &A[i]);
	
	D[N] = 1;
	for (int i = 1;i <= 200;++i)
		C[i] = 1;
	
	for (i = N-1;i >= 1;--i)
	{
		max = 0;
		for (j = N;j > i;--j)
			if (A[i] < A[j])
			{
				if (D[j] > max)
				{
					max = D[j];
					v[i].clear();
					v[i].push_back(j);
					C[i] = C[j];
				}
				else if (D[j] == max)
				{
					v[i].push_back(j);
					C[i]+= C[j];
				}
			}

		D[i] = max + 1;
		if (D[i] > max_i)
		{
			max_i =D[i];
			p = i;
		}
	}
	int nr = 0;
	j = 1;
	

	for (j = 1;j <= N;++j)
		if (D[j] == max_i)
		{
			if (K- C[j] > 0)
				K = K - C[j];
			else
				break;
		}
	
	findNChild(j, nr);
	return 0;
}