Cod sursa(job #2801064)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 14 noiembrie 2021 19:36:49
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;


int a[5001];
int n, l;

void SCLM(int n){


    int *LG = new int[n + 1];
    int pmx = n;

    for(int i = n;i > 0;i--){

        LG[i] = INF;
        int aux = INF;
        for(int j = i + 1;j <= n;j++)
            if(a[i] <= a[j] && a[j] < aux && LG[i] >= LG[j] + 1)
                aux = a[j], LG[i] = LG[j] + 1;

       if(LG[i] > n) 
            LG[i] = 1;

        if(LG[i] >= LG[pmx])
            pmx = i;
    }

    g << LG[pmx] << "\n";
    int poz = 0;
    for(int i = LG[pmx];i >= 1;i--){

        int mn = INT_MAX, p = 0;
        for(int k = poz + 1;k <= n - i + 1;k++)
            if(LG[k] == i && a[k] >= a[poz] && mn > a[k])
                p = k, mn = a[k];

        poz = p;
        g << p << " ";
    }

    delete[] LG;
}

int main(){

    f >> n;
    for(int i = 1, x;i <= n;i++){
        f >> x;
        a[++l] = x;
    }

    SCLM(l);
}