Cod sursa(job #3200284)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 4 februarie 2024 10:45:41
Problema Subsir 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, maxi[5005], a[5005], dp[5005], k, ind[5005];

int main()
{
    f >> n;
    for(int i = 1; i <= n; i ++)
        f >> a[i];

    for(int i = 1; i <= n; i ++)
    {
        int p = lower_bound(maxi + 1, maxi + k + 1, a[i]) - maxi;
        if(p > k)
            k ++;
        maxi[p] = a[i];
        dp[i] = p;
        ind[i] = i;
    }

    for(int i = 1; i <= n; i ++)
        for(int j = i + 1; j <= n; j ++)
            if(dp[i] > dp[j])
            {
                swap(dp[i], dp[j]);
                swap(a[i], a[j]);
                swap(ind[i], ind[j]);
            }

    g << k << '\n';

    int nr = a[1], poz = ind[1], l = 1, u = INT_MIN;
    for(int i = 2; i <= n; i ++)
    {
        if(dp[i] == l && a[i] > u)
        {
            if(nr > a[i])
            {
                poz = ind[i];
                nr = a[i];
            }
        }

        else if(dp[i] != l)
        {
            g << poz << " ";
            l ++; u = nr;
            nr = a[i]; poz = ind[i];
        }
    }

    g << poz;
    return 0;
}