Cod sursa(job #164656)

Utilizator scvalexAlexandru Scvortov scvalex Data 24 martie 2008 17:33:03
Problema Subsir 2 Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <iostream>
#include <fstream>

using namespace std;

int N,
	V[5000];

int cnt[5000],
	p[5000];

int main(int argc, char *argv[]) {
	FILE *fi = fopen("subsir2.in", "r");
	fscanf(fi, "%d", &N);
	for (int i(0); i < N; ++i)
		fscanf(fi, "%d", V + i);
	fclose(fi);

	for (int i = N - 1; i >= 0; --i) {
		int m = 0,
			mj = -1;
		for (int j = N - 1; j > i; --j)
			if (V[j] > V[i])
				if ((cnt[j] > m) || ((cnt[j] == m) && (V[j] < V[mj])))
					m = cnt[j],
					mj = j;
		cnt[i] = m + 1;
		p[i] = mj;
	}

	int m = -1,
		mj = 0;
	for (int i(0); i < N; ++i)
		if (cnt[i] > m)
			m = cnt[i],
			mj = i;

	FILE *fo = fopen("subsir2.out", "w");
	fprintf(fo, "%d\n", m);
	for (int i = mj; i != -1; i = p[i])
		fprintf(fo, "%d ", i + 1);
	fprintf(fo, "\n");
	fclose(fo);

	return 0;
}