Pagini recente » Borderou de evaluare (job #2868399) | Borderou de evaluare (job #2050180) | Cod sursa (job #2603866)
#include <fstream>
#include <unordered_map>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
using L = long;
using UL = unsigned long;
const L INF = LONG_MAX;
UL N;
vector<L> nrs;
void print_LIS(UL i, unordered_map<UL, UL> &prev)
{
static ofstream fout("scmax.out", ios::app);
if (prev[i] != 0)
{
print_LIS(prev[i], prev);
}
fout << nrs[i] << " ";
}
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, UL> prev;
dp[0] = -INF;
indices[-INF] = 0;
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";
print_LIS(indices[dp[index_last_elem]], prev);
}