Cod sursa(job #2079569)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 1 decembrie 2017 15:55:10
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>
#define inf INT_MAX

using namespace std;

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

int a[5001],l[5001];

int main() {
    int n,i,mn,mx,j;
    f>>n;
    for(i=1; i<=n; i++)
        f>>a[i];
    for(i=n; i>=1; i--) {
        mn=inf;
        for(j=i+1; j<=n; j++)
            if(a[j]>=a[i]&&a[j]<mn) {
                mn=min(mn,a[j]);
                l[i]=min(l[i],l[j]+1);
                if(!l[i])
                    l[i]=l[j]+1;
            }
        if(l[i]==0)l[i]=1;
    }
    mn=inf;
    mx=inf;
    for(i=1; i<=n; i++) {
        if(a[i]<mn) {
            mn=a[i];
            mx=min(mx,l[i]);
        }
    }
    g<<mx<<'\n';
    int w=-inf,k,poz=0;
    for(k=mx; k>0; k--) {
        mn=inf;
        mx=inf;
        for(i=poz+1; i<=n; i++)
            if(l[i]==k && a[i]>=w && a[i]<mn) {
                poz=i;
                mn=a[i];
            }
            else
                if(a[i]>=w && a[i]<mn)
                    mn=a[i];
        g<<poz<<" ";
        w=a[poz];
    }
    return 0;
}