261.java

public class TaskAcmpFast {

    int n;
    int m;
    int k;
    boolean[] used;
    String[] tickets;
    long[] wins;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        n = in.readInt();
        m = in.readInt();
        k = in.readInt();
        wins = new long[m + 1];
        for (int i = 1; i <= m; i++) {
            wins[i] = in.readInt();
        }
        tickets = new String[n];
        for (int i = 0; i < n; i++) {
            tickets[i] = in.next();
        }
        Arrays.sort(tickets);
        used = new boolean[k];
        out.println(rec(1, 0, n - 1, 0));
    }


    /**
     *
     * @param d текущий разряд (1-индексация)
     * @param l левая граница подмассива зрителей, которые ещё не выиграли (они выиграют позже, так как префикс совпадает)
     * @param r правая граница подмассива зрителей (см. выше)
     * @param prev сколько выиграли зрители, если считать что мы зафиксировали префикс [0 .. d - 2].
     * Иными словами, prev выигрыш зрителей, у которых префикс перестал совпадать на разряде раньше чем d - 1.
     * @return
     */
    public long rec(int d, int l, int r, long prev) {
        if (d > m) {
            //если мы собрали билет длиной больше чем m, то добавляем к prev выигрыш зрителей l..r
            return prev + (r - l + 1) * wins[d - 1];
        }
        Arrays.fill(used, false);
        //проверяем есть ли у нас незанятая цифра на разряде d
        for (int i = l; i <= r; i++) {
            used[Character.getNumericValue(tickets[i].charAt(d - 1))] = true;
        }
        //если есть, то возвращаем результат, ибо лучше мы не сделаем
        for (int i = 0; i < k; i++) {
            if (!used[i]) {
                return prev + (r - l + 1) * wins[d - 1];
            }
        }
        //иначе рекурсивно делим подмассив [l .. r] на подмассивы с одинаковыми цифры на разряде d
        long min = Long.MAX_VALUE;
        long win = 0;
        for (int i = l, j = l; i <= r; ) {
            for (; j <= r; j++) {
                if (tickets[i].charAt(d - 1) != tickets[j].charAt(d - 1)) {
                    break;
                }
            }
            //win = сколько зрители выиграют на d - 1 позиции
            win = ((r - l + 1) - (j - i)) * wins[d - 1];
            min = Math.min(min, rec(d + 1, i, j - 1, prev + win));
            i = j;
        }
        return min;
    }
}