Cod sursa(job #3332087)

Utilizator Octa-pe-infoNechifor Octavian Octa-pe-info Data 4 ianuarie 2026 00:11:08
Problema Subsir 2 Scor 47
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

int main()
{

    int n;
    fin>>n;

    vector<int>a(n+1),pr(n+1,-1),dp(n+1,0),mx_sfx(n+1,1);

    vector<int>rez;

    for(int i=1;i<=n;i++){

        fin>>a[i];
    }

    int mx = -1;

    for(int i=n;i>=1;i--){

        if(a[i] <= mx)
            mx_sfx[i] = 0;

        mx = max(mx,a[i]);
    }

    for(int i=1;i<=n;i++){

        int mmx = -1;

        int cmb = 0,id=-1;

        for(int j=i-1;j>=1;j--){

            if(mmx < a[j] && cmb < dp[j] && a[j] <= a[i]){

                cmb = dp[j];
                id = j;
            }

            if(a[j] <= a[i])
                mmx = max(mmx,a[j]);
        }

        dp[i] = cmb + 1;
        pr[i] = id;

        if((rez.size() > dp[i] || rez.size() == 0) && mx_sfx[i]){

            rez.clear();

            int j = i;

            while(j != -1){

                rez.push_back(j);
                j = pr[j];
            }

            reverse(rez.begin(),rez.end());
        }
        else if(rez.size() == dp[i] && mx_sfx[i]){

            ///care e mai mic lexicografic

            bool ok = false;

            vector<int>aux;

            int j = i;

            while(j != -1){

                aux.push_back(j);
                j = pr[j];
            }

            reverse(aux.begin(),aux.end());

            for(int k=0;k<aux.size();k++)
                if(a[aux[k]] < a[rez[k]])
                    ok = true;

            if(ok)
                rez = aux;
        }
    }

    fout<<rez.size()<<"\n";

    for(auto i : rez)
        fout<<i<<" ";

    return 0;
}