Cod sursa(job #2397149)

Utilizator bluestorm57Vasile T bluestorm57 Data 4 aprilie 2019 11:10:40
Problema Subsir 2 Scor 36
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>

using namespace std;

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

int n, v[5005];
int best[5005], poz[5005], l[5005], pos, nr;

int gasit ( int i, int j ){
    int li = i;

    if(j == i + 1) return 0;

    for(i = li + 1; i < j; i++)
        if(v[li] <= v[i] && v[i] <= v[j])
            return 1;

    return 0;
}

void see ( int x ){
    g << x << " ";
    if(poz[x] >= 1)
        see(poz[x]);
}

int main(){
    int i, j;
    f >> n;
    if( n == 1){ g << 1 << "\n" << 1; return 0;}
    for(i = 1; i <= n ; i++)
        f >> v[i];

    best[n]=1;
    poz[n]=-1;
    int cmax,pozmax;
    cmax = pozmax = 0;

    for(i = n-1 ; i >= 1; i--){
        best[i] = 1;
        poz[i] = -1;

        for(j = i + 1 ; j <= n; j++)
            if(v[i] <= v[j] && best[i] < best[j] + 1){
                best[i] = best[j] + 1;
                poz[i] = j;

                if(cmax < best[i]){
                    cmax = best[i];
                    pozmax = i;
                }
            }
    }
    g << cmax <<"\n";
    see(pozmax);

    return 0;
}