Cod sursa(job #2833559)

Utilizator RaresRacsanRares Racsan RaresRacsan Data 15 ianuarie 2022 13:21:50
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include  <fstream>

using namespace std;
int a[100002], L[100002], P[100002], n, p, l, pmax, lmax, i, j;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

int main()
{
    fin >> n;

    for(i = 1; i <= n; i++)
    {
        fin >> a[i];
    }
    for(i = n; i >= 1; i--)
    {
        p = i;
        l = 0;
        for(j = i + 1; j <= n; j++)
        {
            if(a[i] <= a[j] && L[j] > l)
            {
                l = L[j];
                p = j;
            }
        }
        L[i] = l + 1;
        P[i] = p;
        if(L[i] > lmax)
            lmax = L[i], pmax = i;
    }
    fout << lmax << '\n';
    p = pmax;
    while(p != P[p])
    {
        fout << p << ' ';
        p = P[p];
    }
    fout << p;
    return 0;
}