Cod sursa(job #584998)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 27 aprilie 2011 18:45:51
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <queue>
#include <fstream>

using namespace std;

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

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

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, vector<element>, compara_ant> q;

int n,i,j,x,nrv;
element e,a[100000],e2;

int main () {
    f >> n;e.h=e.ant=0;q.push(e);e.hant=0;
    for (i=1;i<=n;i++) {
        f >> 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.hant=e.h;e.h=x;q.push(e);
        //for (j=1;j<=nrv;j++) q.push(a[j]);
    }
    e=q.top();
    g << e.ant << '\n';nrv=1;a[1]=e;
    while (e.h!=0) {
        q.pop();e2=q.top();
        while (e2.h!=e.hant) {q.pop();e2=q.top();}
        e=e2;nrv++;a[nrv]=e;
    }
    for (i=nrv-1;i>=1;i--) g<< a[i].h << ' ';

    f.close();g.close();
    return 0;
}