Cod sursa(job #585024)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 27 aprilie 2011 20:35:33
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <queue>
#include <fstream>
#include <deque>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

struct element {
    long long h;
    int ant;
    int ind;
};

struct compara_ant {
    bool operator() (const element& a,const element& b) const {
        if (a.ant==b.ant) return (a.h > b.h);
             else
               return (a.ant < b.ant);
    }
};

priority_queue<element, deque<element>, compara_ant> q;

int n,i,j,nrv,antecedent[100001];
element e,a[100001],e2;
long long h2[100001],x,afis[100001],ela;

int main () {
    f >> n;e.h=e.ant=0;e.ind=0;q.push(e);
    for (i=1;i<=n;i++) {
        f >> x;h2[i]=x;
        nrv=-1;e.h=2000000001;
        while (e.h>=x && q.empty()==false) {
            nrv++;a[nrv]=e;
            e=q.top();q.pop();
        }
        q.push(e);
        e.ant=e.ant+1;e.h=x;antecedent[i]=e.ind;e.ind=i;
        q.push(e);
        for (j=1;j<=nrv;j++) if(!(a[j].h>=e.h && a[j].ant<=e.ant)) q.push(a[j]);
    }
    e=q.top();
    g << e.ant << '\n';
    nrv=e.ind;
    while (nrv!=0) {
        ela++;afis[ela]=h2[nrv];
        nrv=antecedent[nrv];
    }
    for (i=ela;i>=1;i--) g << afis[i] << ' ';
    f.close();g.close();
    return 0;
}