Solution Notes (Jonathan Paulson): Once we put down some wifi station, it covers some interval of cows, and covering the remaining cows is just solving two independent subproblems (the intervals to the left and right of our wifi station). So we might want to look for a dynamic programming solution.

Since every interval covered should start and end at a cow (exercise: prove it), there are only n^2 possible wifi stations we could put down. Since every subproblem starts and ends at a cow, there are n^2 subproblems to consider. So this already gives an O(n^4) dynamic programming solution (for each query interval, try each possible next wifi station). But this is far too slow -- we want O(n^2).

The next observation is that *some* wifi station must cover the leftmost cow, so we might as well place that one next. There are only n wifi stations that cover the first cow (each possible ending position). Furthermore, whenever we put down such a wifi station, we are left with some suffix of the cows that need to be covered, so there are only n subproblems to consider now (put another way, our state is just "how many cows we have covered so far" or "the start of the next interval"). This gives an O(n^2) solution, just what we wanted!

Recap: Let the cow positions be x_1 < x_2 < ... < x_n. Let f(i) be the cost to provide wifi to cows i..n. Then the answer is f(0), and we have the recurrence f(i) = min_{j=i^n} cost(x_i, x_j) + f(j+1), and the base case f(n+1)=0 (the cost to provide wifi to zero costs is 0). Here cost(x1, x2) denotes the cost to provide wifi on [x1,x2] with a single wifi station, which is A+B*(x2-x1)/2.

In fact, it is possible to do better than this DP solution, although it was unnecessary to do so to get full credit. We make the following observation: for a given arrangement of wifi stations, the total cost is S*A + T*B/2 where S is the total number of wifi stations and T is the total length of the line covered by wifi. Consider two adjacent wifi stations, at positions X_1 and X_2 with X_1 < X_2. Suppose the distance between the rightmost cow covered by X_1 and the leftmost cow covered by X_2 is U. So if we replace these two wifi stations with one, the new cost is (S-1)*A + (T+U)*B/2. Then it is advantageous to switch to this new arrangement if A > U*B/2. So we immediately get a linear time solution (after sorting the cows): if two adjacent cows are of distance at least 2*A/B away from each other, then we want to give them different wifi stations. Otherwise, we want to give them the same wifi stations.

#include <cstdio>
#include <algorithm>
using namespace std;

#define NMAX 2000

long long locs[NMAX];

int main() {
    freopen("wifi.in","r",stdin);
    freopen("wifi.out","w",stdout);

    int n;
    long long A, B;
    scanf("%d", &n);
    scanf("%lld", &A);
    scanf("%lld", &B);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &locs[i]);
    }
    sort(locs, locs + n);

    long long nComponents = 1;
    long long totalLength = 0;
    for (int i = 0; i < n - 1; i++) {
        int U = locs[i+1] - locs[i];
        if (U*B > 2*A) {
            nComponents++;
        } else {
            totalLength += U;
        }
    }

    long long totalCostTimes2 = nComponents*A*2 + totalLength*B;
    if (totalCostTimes2 % 2 == 0) {
        printf("%lld\n", totalCostTimes2 / 2);
    } else {
        printf("%lld.5\n", totalCostTimes2 / 2);
    }
}

#include <cstdio>
#include <algorithm>
using namespace std;

#define NMAX 2000

// x-coordinates of the cows
long long locs[NMAX];

// dp[i] will store the minimum cost needed to give coverage
// to the leftmost i cows (0 <= i <= n). Since the minimum cost
// might be a half integer, we actually store twice the cost so
// that we only have to deal with integers.
long long dp[NMAX + 1];

int main() {
    freopen("wifi.in","r",stdin);
    freopen("wifi.out","w",stdout);

    int n;
    long long A, B;
    scanf("%d", &n);
    scanf("%lld", &A);
    scanf("%lld", &B);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &locs[i]);
    }
    sort(locs, locs + n);

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1000000000000000000LL;
        for (int j = 0; j < i; j++) {
            dp[i] = min(dp[i], dp[j] + 2*A + B*(locs[i-1] - locs[j]));
        }
    }

    if (dp[n] % 2 == 0) {
        printf("%lld\n", dp[n] / 2);
    } else {
        printf("%lld.5\n", dp[n] / 2);
    }
}

import java.util.*;
import java.io.*;
import java.awt.Point;
import static java.lang.Math.*;

public class wifi {
    static int n;
    static int A;
    static int B;
    static int[] X = new int[n];
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(new File("wifi.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new
FileWriter("wifi.out")));
        n = in.nextInt();
        A = in.nextInt();
        B = in.nextInt();
        X = new int[n];
        f_s = new boolean[n];
        f = new double[n];
        for(int i=0; i<n; i++) X[i] = in.nextInt();
        Arrays.sort(X);
        double ans = f(0);
        if(abs(ans-(int)(ans+0.5))<1e-9)
            out.println((int)(ans+0.5));
        else out.println(ans);
        out.flush();
    }
    static boolean[] f_s;
    static double[] f;
    static double f(int i) {
        if(i >= n) return 0;
        if(f_s[i]) return f[i];
        f_s[i] = true;
        double ans = 1000.0*1000*1000*1000;
        for(int j=i; j<n; j++) { // end of range
            ans = min(ans, A + B*(X[j]-X[i])/2.0 + f(j+1));
        }
        return f[i] = ans;
    }
}