SRM463 Div1 Medium

500

加算の方が大きくなるのは 2 以下だった気がするので、下限が 1.5 だとある数字の加算が 1 度しか行われないことになる。
また、乗算はそれぞれの数字の差が小さい方が結果が大きくなる。
小さい方から、ある範囲をそれと隣接する範囲へ逆順に加算し、総乗する。

class Nisoku {
public:
  double theMax(vector <double> v)
  {
    const int N = v.size();
    sort(v.begin(), v.end());
    double mx = -1;

    for (int i = 0; i * 2 <= N; ++i) {
      double n = 1;
      const int M = i * 2;
      vector<double> a, b, c;
      for (int j = 0; j < N; ++j) {
        if (j < M) {
          a.push_back(v[j]);
          b.push_back(v[j]);
        } else {
          c.push_back(v[j]);
        }
      }
      reverse(b.begin(), b.end());
      for (int j = 0; j < i; ++j) {
        n *= a[j] + b[j];
      }
      for (int j = 0; j < c.size(); ++j) {
        n *= c[j];
      }
      mx = max(mx, n);
    }

    return mx;
  }
};