SRM536 Div2 Hard

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

view plainprint?

1. class MergersDivTwo {  
2. public:  
3.   double findMaximum(vector <int> R, int k)  
4.   {  
5.     const int N = R.size();  
6.     sort(R.begin(), R.end());  
7.   
8.     vector<double> sum;  
9.     partial_sum(R.begin(), R.end(), back_inserter(sum));  
10.      
11.     double dp[N];  
12.     fill(dp, dp + N, -(1e128));  
13.     dp[0] = R[0];  
14.   
15.     for (int i = 0; i <= N - k; ++i) {  
16.       for (int j = k; i + j <= N; ++j) {         
17.         dp[i + j - 1] = max(dp[i + j - 1], (dp[i] + sum[i + j - 1] - sum[i]) / (double)j);  
18.       }  
19.     }  
20.   
21.     return dp[N - 1];  
22.   }  
23. };  

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];
  }
};