Cod sursa(job #2472632)

Utilizator CharacterMeCharacter Me CharacterMe Data 12 octombrie 2019 17:19:11
Problema Subsir 2 Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
typedef long long ll;
ll n, i, j, sol;
ll left[5001], right[5001], last[5001], list[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(){
    left[1]=right[n]=1;
    for(i=2; i<=n; ++i){
        left[i]=1;
        for(j=1; j<i; ++j){
            if(list[i]>=list[j] && left[j]+1>left[i]) {
                left[i]=left[j]+1;
                last[i]=j;
            }
            else if(list[i]>=list[j] && left[j]+1==left[i] && list[last[i]]>list[j]){
                left[i]=left[j]+1;
                last[i]=j;
            }
        }
    }
    for(i=n-1; i>=1; --i){
        right[i]=1;
        for(j=n; j>i; --j){
            if(list[j]>=list[i] && right[j]+1>right[i]) right[i]=right[j]+1;
        }
    }
    sol=0; left[0]=5001;
    for(i=1; i<=n; ++i) if(right[i]==1 && left[i]<left[sol]) sol=i;
                            else if(right[i]==1 && left[i]==left[sol] && list[i]<list[sol]) sol=i;
}
void write(){
    printf("%lld\n", left[sol]);
    bkt(sol);
}
void bkt(ll pos){
    if(!pos) return;
    bkt(last[pos]);
    printf("%lld ", pos);
}