Cod sursa(job #585003)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 27 aprilie 2011 18:51:24
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 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=-1;e2=e;
    for (i=1;i<=n;i++) {
        f >> x;
        nrv=-1;e.h=2000000001;
        while (e.h>=x && q.empty()==false&&e.hant!=-1) {
            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++) if(a[j].h<e.h||a[j].ant>e.ant) q.push(a[j]);
        q.push(e2);
    }
    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;
}