Cod sursa(job #1977062)

Utilizator taigi100Cazacu Robert taigi100 Data 4 mai 2017 22:13:09
Problema Subsir crescator maximal Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
/*
    Keep It Simple!
*/
#include <fstream>

using namespace std;

const int MAX_N = 100001;

int v[MAX_N], dp[MAX_N], p[MAX_N], N;
int best;
ofstream g("scmax.out");

void ReadInput() {
    ifstream f("scmax.in");
    f >> N;
    for (int i = 1; i <= N; ++i)
        f >> v[i];
}

int binsearch(int x) {
    int left = 1, right = best - 1;
    int ans = 0;
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (v[dp[mid]] > x)
            right = mid-1;
        else {
            ans = mid;
            left = mid + 1;
        }
    }
    return ans;
}

void ComputeDP() {
    int p_best_idx;
    for(int i = 1; i <= N; ++i) {
        if (v[i] > v[dp[best]]) {
            p[i] = dp[best];
            dp[++best] = i;
        } else {
        p_best_idx = binsearch(v[i]);
        p[i] = dp[p_best_idx];
        dp[p_best_idx + 1] = i;
        }
    }
}

void PrintSol(int idx) {
    if (p[idx]) PrintSol(p[idx]);
    g << v[idx] << ' ';
}

void Solve() {
    ReadInput();
    ComputeDP();

    g << best << '\n';
    PrintSol(dp[best]);
}

int main()
{
    Solve();
    return 0;
}