Given a three dimensional table of dimensions N * M * H. N * M is the dimension of the base of the table. H is the number of layers
of the table. You can paint at most T _{ k } cells in k ^{ th } layer with cost of painting a cell in the level being
C _{ k }.

Find out the minimum cost needed to paint such that there is no vertical column which is unpainted on every layer.

QUICK EXPLANATION

You can select exactly N * M cells to paint such that the condition of no vertical column being unpainted is satisfied.

Use greedy algorithm for painting the cells. Paint the least cost N * M cells.

If there are not enough cells available for painting, then answer will be impossible.

EXPLANATION

As said earlier, as cost of each painting each cell is positive, we will not select more than N * M cells.
So we will select N * M cells having least painting cost.

It can be done by using a simple greedy algorithm. We will sort the layers in increasing order of cost and will take the least costly N * M element.

If there are not enough cells available for painting, then the answer will be impossible. In other words, we can say that if the number of cells
available for painting are less than N * M, then the answer is impossible.

Number of cells which can be painted will be T_{ 1 } + T_{ 2 } + â€¦ T_{ k }.

Pseudo Code:

Sort the layers in increasing order of C_k.
toPaint = N * M;
// toPaint number of cells to be painted.
ans = 0
// ans denotes the cost of the operations.
for i = 1 to H:
canPaint = min(toPaint, T_k);
ans += canPaint * C_k
toPaint -= canPaint
if (toPaint > 0):
// it means that you can not paint N * M cells, the answer will be impossible.
print "impossible".
else:
print ans;

Complexity
O(H log H) : We need sorting + another O(H) loop. So time complexity will be O(H log H).

Possible reasons of getting wrong answers
You should make n and m long long rather than int, because n = 10^12 and m = 1 and vice versa.

â€śYour task is to find the minimum cost of painting the table thus that it canâ€™t be seen thought from the top (there is no cell which is unpainted on every layer)â€ť.

Bold text is a bit misleading! Got WAâ€¦ It meant you canâ€™t leave any layer completely unpainted.

Can be solved easily in C++ using the STL map! the index can be the cost, and the corresponding maximum tiles can be the data, i.e., map[c_{k}]+=t_{k}.

I have provided test cases for as much codes as I could have done, please check one other thread in the discussions too where I have given some test cases.

please explain the 1st test case in detail. The problem is still unclear to me. what is meant by table should not be seen through top and no two vertical columns should be unpainted?