Cod sursa(job #1647614)

Utilizator duesakBourceanu Cristian duesak Data 10 martie 2016 21:22:52
Problema Floyd-Warshall/Roy-Floyd Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
using namespace std;
ifstream fin("euro2.in");
ofstream fout("euro2.out");
int poz[10005];
int l[10005];
float v[10005];
int n;
int scm(int in){
    if(in==0)return 0;
    poz[in]=-1;
    l[in]=1;
    int j;
    for(int i=in-1;i>0;i--)
        for(poz[i]=-1,l[i]=1,j=i+1;j<=in;j++)
            if(v[i]<=v[j]&&l[i]<1+l[j]){
                l[i]=l[j]+1;
                poz[i]=j;
            }
    int maxl=l[1];
    for(int i=2;i<=in;i++)
    if(maxl<l[i])maxl=l[i];
    return maxl;
}
int sdm(int in){
    if(in==n)return 0;
    poz[n]=-1;
    l[n]=1;
    int j;
    for(int i=n-1;i>in;i--)
        for(poz[i]=-1,l[i]=1,j=i+1;j<=n;j++)
            if(v[i]>=v[j]&&l[i]<1+l[j]){
                l[i]=l[j]+1;
                poz[i]=j;
            }
    int maxl=l[in+1];
    for(int i=in+1;i<=n;i++)
    if(maxl<l[i])maxl=l[i];
    return maxl;
}
int main(){
    fin>>n;
    int c,vscm,vsdm,maxl=0;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    for(int i=0;i<=n;i++){
        vscm=scm(i);
        vsdm=sdm(i);
        c=vscm+vsdm;
        if(maxl<c)maxl=c;
    }
    fout<<maxl<<'\n';
    fin.close();
    fout.close();
}