Cod sursa(job #2472939)

Utilizator CharacterMeCharacter Me CharacterMe Data 13 octombrie 2019 11:27:40
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
typedef long long ll;
ll n, i, j, sol, maxleft, mr;
ll last[5001], list[5001], val[5001];
bool maxright[5001];
void read();
void solve();
void write();
int main()
{
    freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);
    read();
    solve();
    write();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void read(){
    scanf("%lld", &n);
    for(i=1; i<=n; ++i) scanf("%lld", &list[i]);
}
void solve(){
    maxright[1]=true; mr=list[1];
    for(i=1; i<=n; ++i) if(list[i]<mr){maxright[i]=true; mr=list[i];}
    for(i=n; i>=1; --i){
        maxleft=1000001;
        val[i]=5001;
        for(j=i+1; j<=n; ++j){
            if(maxleft>list[j] && list[j]>=list[i]){
                maxleft=list[j];
                if(val[j]+1<val[i]){
                    val[i]=val[j]+1;
                    last[i]=j;
                }
                else if(val[j]+1==val[i] && list[j]<list[last[i]]) last[i]=j;
            }
        }
        if(val[i]==5001) val[i]=1;
    }
    val[0]=5001;
    for(i=n; i; --i){
        if(!maxright[i]) continue;
        if(val[i]<val[sol]) sol=i;
        else if(val[i]==val[sol] && list[i]<list[sol]) sol=i;
    }
}
void write(){
    printf("%lld\n", val[sol]);
    while(sol){
        printf("%lld ", sol);
        sol=last[sol];
    }
}