Cod sursa(job #2472921)

Utilizator CharacterMeCharacter Me CharacterMe Data 13 octombrie 2019 10:59:07
Problema Subsir 2 Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 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();
void bkt(ll pos);
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[n]=true; mr=list[n];
    for(i=n-1; i>=1; --i) if(list[i]>mr){maxright[i]=true; mr=list[i];}
    for(i=1; i<=n; ++i){
        maxleft=-1000001;
        val[i]=5001;
        for(j=i-1; j; --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]);
    bkt(sol);
}
void bkt(ll pos){
    if(!pos) return;
    bkt(last[pos]);
    printf("%lld ", pos);
}