Cod sursa(job #1426566)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 29 aprilie 2015 22:13:31
Problema Subsir 2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#define DIM 6000
using namespace std;

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

long long N, M, i, j, K, ok, minim, maxim;
long long V[DIM], W[DIM], T[DIM], U[DIM];
long long maxtot, mintot, posfin;

void SetUp(){
     fin >> N;
     for(i = 1; i <= N; i ++)
          fin >> V[i];
     return;
}

void SCMax(){
     for(i = 1; i <= N; i ++){
          maxim = 0; minim = 0;
          for(j = 1; j < i; j ++){
               if(V[j] < V[i]){
                    if(W[j] > maxim){
                         maxim = W[j];
                         minim = V[j];
                         T[i] = j;
                    } else
                    if(W[j] == maxim)
                         if(V[j] < minim){
                              minim = V[j];
                              T[i] = j;
                         }
               }
          }
          W[i] = maxim + 1;
          if(maxtot < W[i]){
               maxtot = W[i];
               posfin = i;
               mintot = V[i];
          } else
          if(maxtot == W[i])
               if(mintot > V[i]){
                    posfin = i;
                    mintot = V[i];
               }
     }
     return;
}

void Rebuild(){
     fout << maxtot << "\n";
     while(posfin){
          U[++K] = posfin;
          posfin = T[posfin];
     }
     for(i = K; i >= 1; i --)
          fout << U[i] << " ";
     return;
}

int main(){
     SetUp();
     SCMax();
     Rebuild();
     return 0;
}