レートの計算式

\[ R=\frac{\sum_{i=1}^k (0.9)^{k-i}Q_i}{\sum_{i=1}^k (0.9)^{k-i}}-\frac{1200}{\sqrt{k}} \]

において、\(k\) を固定して考えると、選ぶコンテストを変えた時に値が変化する部分は. \(\displaystyle \sum_{i=1}^k (0.9)^{k-i}Q_i\) のみであり、さらにこの値に対してレートの値は一次関数的に増加します。 よって、各 \(k=1,2,\ldots,N\) について \(\displaystyle \sum_{i=1}^k (0.9)^{k-i}Q_i\) の最大値 \(M(k)\) が求まれば、問題の答えは

\[ \max_{1\leq k\leq N} \left( \frac{M(k)}{\sum_{i=1}^k (0.9)^{k-i}}-\frac{1200}{\sqrt{k}}\right) \]

として求めることができます。
よって、\(N\) 個のコンテストのうち\(k\) 個を選んだ時の\(\displaystyle \sum_{i=1}^k (0.9)^{k-i}Q_i\) の最大値を各 \(k=1,2,\ldots,N\) に対して求めれば良いです。

これは動的計画法 (DP) によって求めることができます。
\(dp[i][j]\) \((1\leq j\leq i\leq N\) を「\(1\) 回目から \(i\) 回目までのコンテストのうち \(j\) 個を選んだ時の、\(\displaystyle \sum_{k=1}^j (0.9)^{j-k}Q_k\) の最大値(ただし、\((Q_1,Q_2,\ldots,Q_j)\) は選んだコンテストのパフォーマンスを参加順に並べたもの) 」として定義します。 求めたいものは \(dp[N][j]\) \((1\leq j\leq N)\) です。

\(dp[1][1]\) は明らかに \(P_1\) です。
さて、 \(dp[i-1][j']\) \((1\leq j\leq i-1)\) の値が分かっているとして、 \(dp[i][j]\) の計算方法について考えます。

\(i\) 回目までのコンテストの中から \(j\) 個を選ぶ選び方のうち、 \(i\) 回目のコンテストを選ばないような選び方における\(\displaystyle \sum_{k=1}^j (0.9)^{j-k}Q_j\) の最大値は \(dp[i-1][j]\) に一致します。 （ただし、\(j=i\) のときは全てのコンテストを選ぶ必要があるためこの場合はありません。）

\(i\) 回目のコンテストを選ぶような選び方においては、選び方に対するレートの値は

\[ \sum_{k=1}^j (0.9)^{j-k}Q_k=\sum_{k=1}^{j-1} (0.9)^{j-k}Q_k+P_i =0.9\sum_{k=1}^{j-1} (0.9)^{(j-1)-k}Q_k+P_i \]

と書く事ができます。ここで、\((Q_1,Q_2,\ldots,Q_{k-1})\) は \(1\) 回目から \(i-1\) 回目までのコンテストのパフォーマンスの中から(順序を保って)選ぶ必要があることから、 \(\displaystyle \sum_{k=1}^{j-1} (0.9)^{(j-1)-k}Q_k\) の取り得る最大値は \(dp[i-1][j-1]\) と一致します。(ただし、\(j=1\) のときは \(\displaystyle \sum_{k=1}^{j-1} (0.9)^{(j-1)-k}Q_k=0\) です。)

ゆえに、

\[ dp[i][j]= \begin{cases} \max(dp[i-1][1],P_i) & (j=1のとき) \\ \max(dp[i-1][j],0.9\times dp[i-1][j-1]+P_i) & (2\leq j\leq i-1 のとき) \\ 0.9\times dp[i-1][i-1]+P_i & (j=i のとき) \end{cases} \]

として計算することができます。

時間計算量について、各 \(dp[i][j]\) の値は \(dp[i-1][j]\), \(dp[i-1][j-1]\) の値から \(O(1)\) で計算できるため、全体で \(O(N^2)\) で求めることができます。 答えは \(dp[N][j]\) の値から \(O(N)\) で計算できるため、全体で \(O(N^2)\) で解くことができ、十分高速です。
よってこの問題を解くことができました。

別解

\(N\) 個のコンテストのうち\(k\) 個を選んだ時の\(\displaystyle \sum_{i=1}^k (0.9)^{k-i}Q_i\) の最大値を各 \(k=1,2,\ldots,N\) に対して求めれば良い、というところまでは本解法と同じです。

動的計画法によって求める時の定義について、 \(dp[i][j]\) \((1\leq i,j\leq N,j\leq N-i+1)\) を「\(i\) 回目から \(N\) 回目までのコンテストのうち \(j\) 個を選んだ時の、\(\displaystyle \sum_{k=1}^j (0.9)^{j-k}Q_k\) の最大値(ただし、\((Q_1,Q_2,\ldots,Q_j)\) は選んだコンテストのパフォーマンスを参加順に並べたもの) 」として定義します。

このとき、計算の詳細はほぼ同様のため省略しますが、\(dp[N][1]=P_N\) と、

\[ dp[i][j]= \begin{cases} \max(dp[i+1][1],P_i) & (j=1のとき) \\ \max(dp[i+1][j],dp[i+1][j-1]+(0.9)^{j-1}\times P_i) & (2\leq j\leq N-i のとき) \\ dp[i+1][N-i]+0.9^{N-i}\times P_i & (j=N-i+1 のとき) \end{cases} \]

から求めることができます。\(0.9^k\) の値を \(k=0,1,\ldots,N\) について先に計算しておく事によって、やはりこの問題を \(O(N^2)\) で解くことができます。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;
int main(void){
	const double c=0.9;
	int n;
	cin>>n;
	vector<double>p(n);
	vector<double>dp(n+1,0);
	double w,ans=-1200.0;
	for(int i=0;i<n;i++)cin>>p[i];
	for(int i=0;i<n;i++){
		dp[i+1]=c*dp[i]+p[i];
		for(int j=i-1;j>=0;j--){
			dp[j+1]=max(c*dp[j]+p[i],dp[j+1]);
		}
	}
	w=0.0;
	for(int i=1;i<=n;i++){
		w=c*w+1.0;
		ans=max(ans,dp[i]/w-1200.0/sqrt((double)i));
	}
	cout<< std::fixed << std::setprecision(10) <<ans<<endl;
	return 0;
}