まず、\(1\) 日周遊パスのセットを購入する数を \(k\) セット（ \(kD\) 枚）で固定した時に \(N\) 日間の旅行の代金を最小化することを考えます。

\(kD\geq N\) のときは、\(N\) 日間全てを \(1\) 日周遊パスで補うことができ、わざわざ通常料金を払う意味はないため、旅行の代金は \(kP\) 円となります。
なお、この場合において、\(N\) 日間をカバーするための最小セット数, すなわち \(k=\left\lceil \frac{N}{D}\right\rceil\) セット（ただし、\(\lceil x\rceil\) で \(x\) 以上の最小の整数を表す）を超えて購入する必要はないため、\(k=\left\lceil \frac{N}{D}\right\rceil\) の時のみを考えれば良いです。

そうでないとき、すなわち \(0\leq k\leq \left\lceil \frac{N}{D}\right\rceil-1\) のとき、 周遊パスの購入に使った \(kP\) 円に加えて \((N-kD)\) 日分の運賃の通常料金を払う必要があるため、 運賃の通常料金が高い日から順に優先して \(1\) 日周遊パスを使うのが最善となります。すなわち、\(N\) 日間の運賃 \((F_1,F_2,\ldots, F_N)\) を昇順にソートしたものを \((F'_1,F'_2,\ldots, F'_N)\) \((F'_1\leq F'_2\leq \cdots\leq F'_N)\) とすると、\(N\) 日間の旅行にかかる代金の最小値は \(kP+\displaystyle\sum_{i=1}^{N-kD} F'_i\) 円となります。

よって、

• \(k=0,1,\ldots\left\lceil \frac{N}{D}\right\rceil-1\).のときの \(kP+\displaystyle\sum_{i=1}^{N-kD} F'_i\)
• \(\left\lceil \frac{N}{D}\right\rceil P\)

のうちの最小値が答えとなります。 後者の値は \(O(1)\) で計算できます。 前者の値は愚直に計算すると、 \(D=1\) の時に最悪で \(O(N^2)\) かかってしまい、\(2\) 秒の実行時間制限以内に計算を終えることが困難になります。しかし、これはいくつかの方法で \(O(N)\) などで計算することができます。

1. 累積和を用いる方法

先に \(S_j=\displaystyle\sum_{i=1}^{j} F'_i\) を計算することを考えます。これは、\(S_1=F'_1\), \(S_{i+1}=S_i+F'_{i+1}\) \((i=1,2,\ldots N-1)\) で計算でき、求めたい値は \(kP+\displaystyle\sum_{i=1}^{N-kD} F'_i=kP+S_{N-kD}\) として計算できます。
計算量は、\(S_1,S_2,\ldots,S_N\) を求めるのも、 それを用いて、\(kP+\displaystyle\sum_{i=1}^{N-kD} F'_i\) を求めるのもそれぞれ \(O(1)\) でできるため、全体で \(O(N)\) となります。

2.\(kP+\displaystyle\sum_{i=1}^{N-kD} F'_i\) の値を順次求める方法

\(C_k=kP+\displaystyle\sum_{i=1}^{N-kD} F'_i\) とすると、 \(C_{k+1}=C_k+P-\displaystyle\sum_{i=N-(k+1)D+1}^{N-kD} F'_i\) と書けます。
計算量は、\(C_0\) を求めるのに \(O(N)\), \(C_i\) から \(C_{i+1}\) を求めるのに \(O(k)\) かかるため、合計で \(O(N)\) となります。

それぞれの最小値の候補となる値を計算することができれば、後はそのうちの最小のものを出力すれば良いです。

\((F_1,F_2,\ldots,F_N)\) のソートに \(O(N\log N)\)、候補の列挙に \(O(N)\) かかるため、全体の計算量は \(O(N\log N)\) であり、よって十分高速にこの問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,d,k;
  long long p;
  cin>>n>>d>>p;

  vector<long long>f(n),s(n);
  for(int i=0;i<n;i++)cin>>f[i];
  
  sort(f.begin(),f.end());
  s[0]=f[0];
  for(int i=0;i<n-1;i++)s[i+1]=s[i]+f[i+1];

  k=(n+d-1)/d;
  long long ans=p*k;
  for(int i=0;i<k;i++){
    ans=min(ans,s[n-1-(i*d)]+(p*i));
  }

  cout<<ans<<endl;
	return 0;
}