Cod sursa(job #1666887)

Utilizator sebastiannrxRichiteanu Mihai Sebastian sebastiannrx Data 28 martie 2016 14:26:37
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n,i,j,d,mi,ma,k,v[5001],s[5001],l[5001];
int main()
{   f>>n;
    for (i=1;i<=n;++i)
        f>>v[i];
    l[n]=1;
    s[n]=0;

    for (i=n;i>=1;--i) {
        ma=0;
        k=0;
        mi=999999999;
        for (j=i+1;j<=n;++j) {
            if (v[j]>=v[i] && l[j]>=ma) {
                d=v[j]-v[i];
                ma=l[j];
                if (d<=mi) {
                    mi=d;
                    k=j;}}}
        s[i]=k;
        l[i]=ma+1;}

    ma=0;
    for (i=1;i<=n;++i)
        if (l[i]>ma) {
            ma=l[i];
            k=i;}

    g<<ma<<'\n'<<k<<" ";
    k=s[k];
    --ma;
    while (ma) {
        g<<k<<" ";
        k=s[k];
        --ma;
    }
    g<<'\n';






    return 0;
}