Cod sursa(job #1199605)

Utilizator azkabancont-vechi azkaban Data 19 iunie 2014 21:22:46
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <algorithm> 
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");

long n,i,j,A[100013],P[100013],coef,Pbest,pivot,sol(0),Ssol[100013];
int main()
{
    cin>>n;
    for (i=1;i<=n;++i) {
                        cin>>A[i];
                        P[i]=A[i];
                        }
    for (i=2;i<=n;++i){
                       coef=0;
                       Pbest=0;
                       for (j=i-1; j>0;--j) 
                                  if (A[j]<A[i]) Pbest=max(Pbest,P[j]);               
                       P[i]=P[i]+Pbest;           
                      }
    for (i=1;i<=n;++i) {
                        Pbest=max(Pbest,P[i]);
                        if (P[i]==Pbest) pivot=i;
                        }
    while (Pbest!=0) {
                      Pbest-=A[pivot];
                      Ssol[++sol]=A[pivot];
                      for (i=pivot-1;i>=1;--i) if (P[i]==Pbest) {
                                                                 pivot=i;
                                                                 break;
                                                                 }
                      }
    cout<<sol<<"\n";
    for (i=sol;i>=1;--i) cout<<Ssol[i]<<" ";
    
return 0;
}