Cod sursa(job #2398140)

Utilizator bluestorm57Vasile T bluestorm57 Data 5 aprilie 2019 09:11:49
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 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;
bool ok[5005];
int minim = (1<<30);

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];
        if(v[i] < minim){
            minim = v[i];
            ok[i] = 1;
        }
    }

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

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

        for(j = i + 1 ; j <= n ; j++)
            if(v[j] >= v[i] && (best[j] + 1 > best[i] || (best[i] == best[j] + 1 && v[j] < v[poz[i]]) ) /*&& !gasit(i,j)*/ ){
                best[i] = best[j] + 1;
                poz[i] = j; //g << j << " " << i << " " << gasit(i,j)<<"\n";
            }

        if(poz[i] == -1)
            poz[i] = 1;

        if(ok[i] && ( best[i] > cmax || (best[i] == cmax && v[i] < v[pozmax]) )){
            cmax = best[i];
            pozmax = i;
        }

    }

    g << cmax << "\n";

    see(pozmax);

   // g << pozmax << "\n";
    /*for(i = 1 ; i <= n; i++ )
        g << best[i] << " "; g << "\n";
    for(i = 1 ; i <= n; i++ )
        g << poz[i] << " ";*/

    return 0;
}