SRM536 Div2 Hard

1000
ソートしてDPする。意外と時間がかかった。

class MergersDivTwo {
public:
  double findMaximum(vector <int> R, int k)
  {
    const int N = R.size();
    sort(R.begin(), R.end());

    vector<double> sum;
    partial_sum(R.begin(), R.end(), back_inserter(sum));
   
    double dp[N];
    fill(dp, dp + N, -(1e128));
    dp[0] = R[0];

    for (int i = 0; i <= N - k; ++i) {
      for (int j = k; i + j <= N; ++j) {       
        dp[i + j - 1] = max(dp[i + j - 1], (dp[i] + sum[i + j - 1] - sum[i]) / (double)j);
      }
    }

    return dp[N - 1];
  }
};