First, given a fixed number \(k\) of batches of one-day passes (\(kD\) passes), we consider how we can minimize the total cost for the \(N\)-day trip.

If \(kD\geq N\), then all the \(N\) days can be covered by one-day passes, and there is no use paying a regular fare, so the total cost is \(kP\) yen.
In this case, it is useless to buy more batches of passes than the minimum number, \(k=\left\lceil \frac{N}{D}\right\rceil\), of batches (where \(\lceil x\rceil\) denotes the minimum integer greater than or equal to \(x\)), so it is sufficient to consider \(k=\left\lceil \frac{N}{D}\right\rceil\).

Otherwise, that is, if \(0\leq k\leq \left\lceil \frac{N}{D}\right\rceil-1\), Then you have to pay the regular fare for the \((N-kD)\) yen as well as the \(kP\) yen for the passes, so it is optimal to use the passes on the days with highest regular fares. In other words, when the regular fares \((F_1,F_2,\ldots, F_N)\) of the \(N\) days are sorted in ascending order as \((F'_1,F'_2,\ldots, F'_N)\) \((F'_1\leq F'_2\leq \cdots\leq F'_N)\), the minimum total cost for the \(N\)-day trip is \(kP+\displaystyle\sum_{i=1}^{N-kD} F'_i\) yen.

Therefore, the answer is minimum value among

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

The latter value can be computed in an \(O(1)\) time. The latter costs at worst \(O(N^2)\) time for \(D=1\), which makes it difficult to finish computing within the execution time limit of two seconds. However, there are several tricks to finish it in a total of \(O(N)\) time.

1. using cumulative sums

We precompute \(S_j=\displaystyle\sum_{i=1}^{j} F'_i\). They can be found by \(S_1=F'_1\), \(S_{i+1}=S_i+F'_{i+1}\) \((i=1,2,\ldots N-1)\) time, so the sought value is found as \(kP+\displaystyle\sum_{i=1}^{N-kD} F'_i=kP+S_{N-kD}\).
Both finding \(S_1,S_2,\ldots,S_N\) and using them to compute \(kP+\displaystyle\sum_{i=1}^{N-kD} F'_i\) costs \(O(1)\) time each, so the total complexity is \(O(N)\).

2. finding \(kP+\displaystyle\sum_{i=1}^{N-kD} F'_i\) successively

Let \(C_k=kP+\displaystyle\sum_{i=1}^{N-kD} F'_i\); then we find \(C_{k+1}=C_k+P-\displaystyle\sum_{i=N-(k+1)D+1}^{N-kD} F'_i\).
The complexity is \(O(N)\) to find \(C_0\) and \(O(k)\) to find \(C_{i+1}\) from \(C_i\), for a total of \(O(N)\).

Once we find the candidates for the minimum values, all that left is to print the minimum among them.

Sorting \((F_1,F_2,\ldots,F_N)\) costs \(O(N\log N)\) time, and enumerating the candidates costs \(O(N)\), so the overall complexity is \(O(N\log N)\), which is fast enough to solve this problem.

Sample code in 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;
}