Cod sursa(job #1560098)

Utilizator geni950814Geni Geni geni950814 Data 1 ianuarie 2016 18:32:17
Problema Subsir crescator maximal Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 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;
        }
    }
    
    int result = max(dq[1] - dq[0], N - dq[2]);
     
    if(result != (dq[1] - dq[0])) {
        dq.pop_front();
        dq.pop_front();
        dq.push_back(N);
    }

    printf("%d", result);
    cout << endl;
    for(int i = dq[0]; i < dq[1]; i++) {
        printf("%d", V[i]);
        printf("%c", ' ');
    }
    return 0;
}