Pagini recente » Cod sursa (job #1175953) | Monitorul de evaluare | Cod sursa (job #1760296) | Cod sursa (job #2424768) | Cod sursa (job #1175950)
#include <stdio.h>
#include <iostream>
#include <fstream>
using namespace std;
#define in "scmax.in"
#define out "scmax.out"
#define MAXN 100001
int n, arr[MAXN], best[MAXN], parent[MAXN], maxi;
void read_input()
{
ifstream fin(in);
if (fin.is_open())
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> arr[i];
//cout << arr[i] << ' ';
}
fin.close();
}
}
int get_parent_index(int ci)
{
int pi = 0;
int cval = arr[ci];
int max = 0;
for (int i = 1; i < ci; ++i)
{
if (arr[i] >= max && arr[i] < cval)
{
max = arr[i];
pi = i;
}
}
return pi;
}
void resolve()
{
int pi;
for (int i = 1; i <= n; ++i)
{
pi = get_parent_index(i);
parent[i] = pi;
best[i] = best[pi] + 1;
if (best[i] > best[maxi])
{
maxi = i;
}
}
}
void print_debug()
{
cout << '\n';
for (int i = 1; i <= n; ++i)
{
cout << best[i] << ' ';
}
}
void print_solution()
{
ofstream fout(out);
int sol[MAXN];
int max_len = best[maxi];
int k = max_len;
while (maxi > 0)
{
sol[--k] = arr[maxi];
maxi = parent[maxi];
}
fout << max_len << '\n';
for (int i = 0; i < max_len; ++i)
{
fout << sol[i] << ' ';
}
}
int main()
{
read_input();
resolve();
//print_debug();
print_solution();
//char x;
//cin >> x;
return 0;
}