Pagini recente » Borderou de evaluare (job #767797) | Cod sursa (job #1291774) | Cod sursa (job #2603870)
#include <fstream>
#include <unordered_map>
#include <vector>
#include <climits>
#include <algorithm>
#include <ios>
#include <stack>
using namespace std;
using L = long long;
using UL = long long;
const L INF = LONG_MAX;
UL N;
vector<L> nrs;
int main()
{
ifstream fin("scmax.in");
fin >> N;
nrs.reserve(N);
for (UL i = 0; i < N; ++i)
{
fin >> nrs[i];
}
vector<L> dp(N + 1, INF);
unordered_map<L, UL> indices;
unordered_map<UL, L> prev;
dp[0] = -INF;
indices[-INF] = -1;
for (UL i = 0; i < N; ++i)
{
UL j = upper_bound(dp.begin(), dp.end(), nrs[i]) - dp.begin();
if (dp[j - 1] < nrs[i] && nrs[i] < dp[j])
{
dp[j] = nrs[i];
prev[i] = indices[dp[j - 1]];
indices[dp[j]] = i;
}
}
ofstream fout("scmax.out");
UL index_last_elem = lower_bound(dp.begin(), dp.end(), INF) - dp.begin() - 1;
fout << index_last_elem << "\n";
stack<UL> LIS;
for (UL i = indices[dp[index_last_elem]]; index_last_elem--; i = prev[i])
{
LIS.emplace(nrs[i]);
}
while (!LIS.empty())
{
fout << LIS.top() << " ";
LIS.pop();
}
}