### PROBLEM LINK:

**Author:** Dmytro Berezin

**Tester:** Hiroto Sekido, Gerald Agapov

**Editorialist:** Ajay K. Verma

### DIFFICULTY:

Easy

### PREREQUISITES:

Ad-hoc, Sorting

### PROBLEM:

We are given a list of N cells, and a set of M colors, with each cell having a color initially (specified by array A). If a cell has a given color, it fetches some points which are specified by a two-dimensional matrix B. It is also possible to recolor a cell with a different color, but it has a cost which is specified by a two-dimensional matrix C. The goal is perform at most k recolorings for a given k such that the gain (the points obtained from cell colors - cost of recolorings) is maximum.

### QUICK EXPLANATION:

If we do not perform any recoloring, the gain would be the sum of B[i][A[i]] values (The contribution of i-th cell is B[i][A[i]]). For each cell, compute the maximum increment in its contribution that can be obtained by recoloring, and pick the k cells with highest increments.

### EXPLANATION:

Assume that we do not perform any recolorings, in that case there will be no cost for recolorings, and the gain would be the sum of points obtained from cell colors.

Since the color of i-th cell is A[i], it will fetch B[i][A[i]] points. We will call this value as the contribution of i-th cell. The total gain will be the sum of the contributions of all cells.

Now, it is possible that we can increase the contribution of a cell by recoloring it. For example, if we recolor i-th cell with color j, it will cost us C[i][j], and the points that it will fetch will be B[i][j], which could be so large that it may compensate the cost of recoloring. More formally,

old contribution = B[i][A[i]],

cost of recoloring = C[i][j],

new contribution = B[i][j],

net gain = (B[i][j] - B[i][A[i]]) - C[i][j].

Now if the net gain is negative, then there is no point of recoloring the i-th cell with j-th color, however, if it is positive, recoloring this cell would bring us more points. For each cell i, try all possible recoloring of it, and pick the one which maximizes the net gain. We denote the maximum net gain of i-th cell as delta[i]. The following code computes the delta values for all cells.

for (int i = 0; i < N; ++i) { delta[i] = 0; for (int j = 0; j < M; ++j) delta[i] = max(delta[i], B[i][j] - B[i][A[i]] - C[i][j]); }

Once we have the maximum net gains of all cells, we need to pick the k cells which have the highest net gains. This could be obtained by sorting or using a more efficient selection algorithm.

### TIME COMPLEXITY:

O (NM + N lg N)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.

Tester’s solution will be put up soon.