|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||9||5||5||71.429%|
Night clubs aren’t what they used to be. Our benevolent state has decided that, for health and safety reasons, every club must now meet a minimum lighting standard. They have moved to verify standards by dividing each club up into 1m2 cells and measuring the light levels on the floor with probes in the centre of each cell.
Club owners aren’t happy about this; they will comply with the letter of the law, but don’t want to spend a penny more than they have to on electricity. Instead of upgrading their lighting, they will fence off the offending parts of the club to deal with later.
You will be given a grid representing a map of the lights in a club. Each cell of the grid (r, c) will have a light directly above its centre with a bulb of strength s, (0 ≤ s ≤ 9).
The ceiling is flat—its height is constant. Each light will affect every nearby cell, increasing the light level at distance (x, y, z) by:
s / (x2 + y2 + z2)
Building a section of transparent fencing between any two cells usually costs £11. However, if the cells on both sides meet the minimum lighting standard, the price per length of fencing rises steeply to £43, as builders find it hard to work under the pulsating night club lights and demand extra compensation.
How much will you have to spend on fencing out the dark spots?
It is guaranteed that the 2(R + C) − 4 cells along the borders of the club are sufficiently lit.
9 1 6 6 333333 300003 300003 300003 300003 333333
5 2 6 7 6323226 3000005 2000002 2000002 5000003 6223236