Cod sursa(job #1560100)

Utilizator geni950814Geni Geni geni950814 Data 1 ianuarie 2016 18:50:20
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <deque>
#include <iostream>

using namespace std;

int N, V[100000];
int main() {
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

    scanf("%d", &N);

    deque<int> dq;

    dq.push_back(0);
    
    int elem;
    for(int i = 0; i < N; i++) {
        scanf("%d", &elem);
        while(i > 0 && V[i-1] == elem) {
            scanf("%d", &elem);
            N--;
        }
        V[i] = elem;
        //cout << "i: " << i << endl;
        if(i > 0) {
        //cout << "(" << V[i-1] << ", " << V[i] << ")" <<  endl;
        }
        if(i > 0 && V[i-1] > V[i]) {
            //cout << "CHEKING: " << dq.size() << endl;
            if(dq.size() > 2) {
                if((i-dq[2]) > (dq[1] - dq[0])) {
                    //cout << "popping out: " << dq.front() << endl;
                    dq.pop_front();
                    //cout << "popping out: " << dq.front() << endl;
                    dq.pop_front();
                    //cout << "pushing in: " << i << endl;
                    dq.push_back(i);
                } else {
                    //cout << "poping out back: " << dq.back() << endl;
                    dq.pop_back();
                }
            } else {
                dq.push_back(i);                    
                //cout << "pushing in: " << i << endl;
            }
            dq.push_back(i);
            //cout << "pushing in: " << i << endl;
        }
    }
    
    dq.push_back(N);
    
    if(dq.size() > 2) {
        if((dq[1]-dq[0]) < (dq[3]-dq[2])) {
            dq.pop_front();
            dq.pop_front();
        }
    }
     
    printf("%d", dq[1] - dq[0]);
    cout << endl;
    for(int i = dq[0]; i < dq[1]; i++) {
        printf("%d", V[i]);
        printf("%c", ' ');
    }
    return 0;
}