PROBLEM STATEMENT
Little Dazdraperma likes drawing a lot. She drew some red points on the plane. The coordinates of
these points are given in vector x and vector y, where the i-th point is located at
(x[i], y[i]). Her friend sells blue squares of different types. A square of type i has sides of
length sides[i] and a cost of cost[i] assigned to it. She thinks that her picture will be more
attractive if all the red points would be covered by squares (possibly overlapping). She decided
that the sides of all the squares must be parallel to either the x or y axis. The point A is
considered to be covered by a square if it lies inside it or on its boundary.
Now she wonders what is the smallest amount of money she has to spend to cover all red points with
blue squares. Note that there is an unlimited amount of squares of each type and if Dazdraperma
wants to buy several squares of the same type, she must pay the corresponding cost for each single
square. Return the minimum cost for covering all red points with the given squares.
DEFINITION
Class:SquaresCovering
Method:minCost
Parameters:vector , vector , vector , vector
Returns:int
Method signature:int minCost(vector x, vector y, vector cost, vector sides)
CONSTRAINTS
-x will contain between 1 and 16 elements, inclusive.
-y will contain the same number of elements as x.
-Each element of x will be between 0 and 1000000000 (109), inclusive.
-Each element of y will be between 0 and 1000000000 (109), inclusive.
-cost will contain between 1 and 50 elements, inclusive.
-sides will contain the same number of elements as cost.
-Each element of sides will be between 1 and 1000000000 (109), inclusive.
-Each element of cost will be between 1 and 100000000 (108), inclusive.
EXAMPLES
0)
{1,100}
{1,100}
{3,1}
{100,1}
Returns: 2
Here it is better to cover each point with its own square of size 1.
1)
{1,100}
{1,100}
{1,1}
{100,1}
Returns: 1
Here it is better to cover both points with one square of size 100.
2)
{0,100,201,300}
{0,0,1,0}
{6,100,10}
{1,100,99}
Returns: 22
In this test case it is better to cover points 0 and 1 with their own squares of size 1 and points
2 and 3 with one square of size
99.
3)
{41,6334,19169,11478,26962,5705,23281,41}
{18467,26500,15724,29358,24464,28145,16827,18467}
{292,11943,5437,14605,154,12383,18717,19896,21727,11539,19913,26300,9895,23812,30334,4665,7712,6869,27645,32758}
{9962,2996,4828,32392,33,293,17422,19719,5448,14772,1870,25668,17036,28704,31323,17674,15142,28254,25548,32663}
Returns: 738
Note that red points can coincide.
4)
{41,6334,9169,1478,6962,5705,3281}
{8467,6500,5724,9358,4464,8145,6827}
{92,43,37,15,54,83,17,96,27,39,13,100,95,12,34,65,12,69,45,58}
{962,996,828,392,903,293,422,719,448,772,870,668,36,704,323,674,142,254,548,663}
Returns: 84