Cod sursa(job #1112158)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 19 februarie 2014 15:01:41
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <set>

using namespace std;

int N,A[1005],B[1005],m,p;

std::set< pair< int,pair< int,int> > > SET;
std::set< pair< int,pair<int,int > > > :: reverse_iterator it;

int main()
{
    ifstream f("scmax.in");
    f>>N;
    for(int i=1;i<=N;i++) f>>A[i];


    int X,Y;
    for( int i=N; i>=1 ; --i ){
        X=1;Y=0;
        it = SET.rbegin();
        while( it!= SET.rend() && (*it).second.first<= A[i]   ) it++;
        if( it!= SET.rend() ){
            X= (*it).first +1;
            Y= (*it).second.second;
        }
        SET.insert (  make_pair(X , make_pair(A[i],i) ));
        B[i]=Y;
        if( X>=m ) {m=X;p=i;}    }
    ofstream g("scmax.out");
    it = SET.rbegin();
    int k=(*it).first ;
    g<< k  <<'\n';
    int i=p;
    //g<<i<<" ";
    do{
        g<<A[i]<<" ";
        i=B[i];
    }while(i!=0);


    return 0;
}