Cod sursa(job #1015620)

Utilizator asortofBarbu Iulian asortof Data 24 octombrie 2013 21:35:30
Problema Subsir crescator maximal Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[100001],l[100001],Max=0,Lmax=0,i,poz,poz1,n;
void cb(int st,int dr)
{int m=(st+dr)/2;
 if(st==dr){if(a[st]<a[st+1] && l[st]>Max) Max=l[st];
            else if(a[st]>a[st+1])  Max=0;
            l[st+1]=Max+1;
            if(Max==1 && st<poz) poz=st;
            if(l[st+1]>=Lmax) {Lmax=l[st+1];  poz1=poz;}}
 else {cb(st,m);
       cb(m+1,dr);}}
void afis()
{int x;
 g<<Lmax<<endl;
 g<<a[poz1]<<" ";
 x=a[poz1]; Lmax--;
 for(int i=poz1+1;i<=n;i++)
  if(a[i]>x && Lmax>0)
  {Lmax--;
   g<<a[i]<<" ";
   x=a[i];}}
int main()
{f>>n; for(i=1;i<=n;i++) f>>a[i];
 l[1]=1; poz=n;
 cb(1,n);
 afis();
 return 0;
}