Cod sursa(job #2743899)

Utilizator cdragomirDragomir Constantin-Cristian cdragomir Data 23 aprilie 2021 17:27:47
Problema Subsir crescator maximal Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>

using namespace std;

int main() {
	ifstream fin("scmax.in");
	ofstream fout("scmax.out");
	uint64_t N;
	fin >> N;
	N++;
	int64_t *v = (int64_t *)malloc(sizeof(int64_t) * N);
	uint64_t i, j;
	for (i = 1; i < N; i++) {
		fin >> v[i];
	}

	int64_t *dp = (int64_t *)malloc(sizeof(int64_t) * N);
	int64_t *prec = (int64_t *)malloc(sizeof(int64_t) * N);
	dp[1] = 1;
	prec[1] = 1;
	for (i = 2; i < N; i++) {
		int64_t index_dp = -1;
		for (j = 1; j < i; j++) {
			if (v[i] > v[j]) {
				if ((index_dp != -1 && dp[j] > dp[index_dp]) || index_dp == -1) {
					index_dp = j;
				}
			}
			if (index_dp != -1) {
				dp[i] = 1 + dp[index_dp];
				prec[i] = index_dp;
			} else {
				dp[i] = 1;
				prec[i] = 1;
			}
		}
	}

	int64_t sol = dp[1];
	int64_t index_sol = 1;
	for (i = 2; i < N; i++) {
		if (dp[i] > sol) {
			sol = dp[i];
			index_sol = i;
		}
	}
	fout << sol << '\n';
	int64_t *best_subseq = (int64_t *)malloc(sizeof(int64_t) * sol);
	int64_t cnt = 0;
	while (index_sol != prec[index_sol]) {
		best_subseq[cnt++] = v[index_sol];
		index_sol = prec[index_sol];
	}

	int64_t k;
	for (k = sol - 1; k > -1; k--) {
		fout << best_subseq[k] << ' ';
	}
	fout << '\n';
}