Problem: Example

Input

2
10 10


Output

40.00000000

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,int> pdi;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF -1

int n;

bool used_start[500];
bool used_end[500];

#define MAX_V 505
struct edge{int to;double cost;};
vector<edge> G[MAX_V];
double d[MAX_V];

void dijkstra(int s,int V){
    priority_queue< pdi,vector<pdi>> que;
    rep(i,MAX_V)d[i]=INF;
    d[s]=0;
    que.push(pdi(0,s));
    
    while(que.size()){
        pdi p=que.top();
        que.pop();
        
        int v=p.second;
        if(d[v]>p.first)continue;
        
        rep(i,G[v].size()){
            edge e=G[v][i];
            if(d[e.to]<d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(pdi(d[e.to],e.to));
            }
        }
    }
}


void add_edge_start(vector<int> data){
    double now=0;
    rep(i,n){
        double r = data[i];
        if(now<(sqrt(2)-1)*r){
            now = (sqrt(2)+1)*r;
            used_start[i]=true;
//            cout<<"501"<<"->"<<i<<" "<<r<<endl;
            G[501].pb(edge{(int)i,r});
        }
        else break;
    }
}


void add_edge_end(vector<int> data){
    double now=0;
    for(int i=n-1;i>=0;i--){
        double r = data[i];
        if(now<(sqrt(2)-1)*r){
            now = (sqrt(2)+1)*r;
            used_end[i]=true;
//            cout<<i<<"->"<<"502 "<<r<<endl;
            G[i].pb(edge{502,r});
        }
        else break;
    }
    
}


void connect(int p,vector<int> data){
    double r=data[p];           //???p?????????
    double x=0,y=r;             //?????????????????§?¨?
    double l=0;                 //???p??????????????????i??????????????§????§?????????¢
    bool connected = false;     //???p??¨?????????????????¨?????????????????????
    int dist=-1;                //???p????????????????????????(???p -> ???dist???????????????)
    double wait=-1;             //???p????????????????????§?????????
    
    for(int i=p+1;i<n;i++){
        double rd = data[i];    //???i?????????
        double tx = x, ty = y, tr=data[i-1];
        
        if( (rd+tr)*(rd+tr) - abs(rd-y)*abs(rd-y) <= 0  )continue;      //sqrt(~~~)???nan?????????????????????
        x += sqrt( (rd+tr)*(rd+tr) - abs(rd-tr)*abs(rd-tr) );           //???j??????????????§?¨?????§????
        y = rd;
        
        
        if( (x)*(x)+(y-r)*(y-r)<=(r+rd)*(r+rd)+1e-7 ){      //??¨???????????????????????????
            x = sqrt( (r+rd)*(r+rd) - abs(r-rd)*abs(r-rd) );
            y = rd;
            
            if(  (used_start[p]&&used_start[i]) || (used_end[p]&&used_end[i])  ){}
            else{
                //                cout<<endl<<p<<"->"<<i<<" "<<x<<endl;
                G[p].pb(edge{i,x});
            }
        }
    }
}


void add_edge(vector<int> data){
    rep(i,n-1){
        connect(i,data);
    }
}



int main(){
    cin>>n;
    vector<int> data(n);
    rep(i,n)cin>>data[i];
    
    rep(i,500)used_start[i] = used_end[i] = false;
    
    add_edge_start(data);
    
    add_edge_end(data);
    
    add_edge(data);
    
    
    dijkstra(501,MAX_V);
    
    printf("%.10lf\n",d[502]);
}