Cod sursa(job #2022230)

Utilizator Bodo171Bogdan Pop Bodo171 Data 16 septembrie 2017 00:09:10
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <iostream>
#include <fstream>
using namespace std;
int best[5005],nxt[5005],v[5005];
int i,j,n,mn;
int main()
{
    ifstream f("subsir2.in");
    ofstream g("subsir2.out");
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    v[0]=-(1<<30);
    for(i=n;i>=0;i--)
    {
        mn=(1<<30);
        for(j=i+1;j<=n;j++)
        {
            if(best[j]>=best[i]&&v[j]<mn&&v[j]>=v[i])
                best[i]=best[j],nxt[i]=j;
            if(v[j]<mn&&v[j]>=v[i])
                mn=v[j];
        }
        if(!nxt[i])
            nxt[i]=n+1;
        best[i]++;
    }
    g<<best[0]-1<<'\n';
    i=0;
    while(i<=n)
    {
        if(nxt[i]<=n) g<<nxt[i]<<' ';
        i=nxt[i];
    }
    return 0;
}