Cod sursa(job #2467637)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 4 octombrie 2019 19:04:26
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5005;

int v[MAXN], last[MAXN];
vector<int> dp, ans;
int n;

void scmax(){
    dp.push_back(0);
    for(int i = 1; i <= n; ++i){
        if(v[i] > v[dp.back()]){
            last[i] = dp.back();
            dp.push_back(i);
            continue;
        }
        int rez = 0, pas = 1 << 30;
        while(pas){
            if(rez + pas < (int)dp.size() && v[dp[rez + pas]] < v[i])
                rez += pas;
            pas /= 2;
        }
        rez++;
        last[i] = dp[rez - 1];
        dp[rez] = i;
    }
    int curent = dp.back();
    while(curent){
        ans.push_back(curent);
        curent = last[curent];
    }
    reverse(ans.begin(), ans.end());
}

int main()
{
    ifstream fin("subsir2.in");
    ofstream fout("subsir2.out");
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> v[i];
    scmax();
    fout << ans.size() << "\n";
    for(auto x:ans) fout << x << " ";
    return 0;
}