Cod sursa(job #2382220)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 17 martie 2019 21:25:55
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
#define N 5005

using namespace std;

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

int dp[N] , tt[N] , t[N] ;
stack<int> st;

int main()
{
    int n , i , j , xx , maxim=0;
    fin >> n ;
    for ( i = 1 ; i <= n ; i++ )
    {
        fin >> t[i] ;
        dp[i] = 1 ;
        for ( j = 1 ; j < i ; j++ )
        {
            if ( t[i] > t[j] )
            {
                if ( dp[i] < dp[j]+1 )
                {
                    dp[i] = dp[j]+1 ;
                    tt[i] = j ;
                }
                else if ( dp[i] == dp[j]+1 && t[tt[i]] > t[j] )
                    tt[i] = j ;
            }
        }
    }
    for ( i = 1 ; i <= n ; i++ )
    {
        if ( maxim < dp[i] )
        {
            maxim = dp[i] ;
            xx = i ;
        }
        else if ( maxim == dp[i] && t[tt[xx]] > t[tt[i]] )
            xx = i ;
        else if ( maxim == dp[i] && t[tt[xx]] == t[tt[i]] && t[xx] > t[i] )
            xx = i ;
    }
    fout << maxim << '\n' ;
    while ( xx )
    {
        st.push(xx) ;
        xx = tt[xx] ;
    }
    while ( !st.empty() )
    {
        fout << st.top() << " " ;
        st.pop() ;
    }
}