Problem: Example

Input

2
10 10


Output

40.00000000

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
// Brute Force Attack!
int main(int argc, char *argv[])
{
  int n;
  cin >> n;
  vector<int> rs;
  double d = 0;
  for(int i = 0; i < n; i++) {
    int r;
    cin >> r;
    rs.push_back(r);
  }
  // locating greedily!
  vector<double> xs;
  double xmax = 0;
  auto touching = [&xs,&rs](int j, int i) {
    double xj = xs[j];
    int rj = rs[j];
    int ri = rs[i];
    // xi^2 + (ri - rj)^2 = (ri + rj)^2
    // xi = \sqrt{ (ri + rj)^2 - (ri - rj)^2 }
    double xi = 2 * sqrt( ri * rj );
    return xi + xj;
  };
  for(int i = 0; i < n; i++) {
    double x = rs[i]; // touching the wall
    for(int j = i - 1; j >= 0; j--) {
      double xx = touching(j, i);
      if(xx > x) x = xx;
    }
    xs.push_back(x);
    xmax = max(xmax, x + rs[i]);
  }
  cout << setprecision(16) << xmax << endl;
  
  return 0;
}