| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 19 | 9 | 8 | 44.444% |
You have $N$ magic squares (numbered from 1ドル$ to $N$). For each magic square, you can set the length of its side to any non-negative integers. The cost of each magic square is proportional to its area; magic square $i$ has a cost of $C_i$ per unit area. In other words, if the length of magic square $i$ is set to $k,ドル then it will cost you $k^2 \cdot C_i$.
You want to build a wall with a length of $D$ using these magic squares. You have to line up all your magic squares next to each other, and their total length has to be exactly $D$. The base of each magic square must fully touch the floor, i.e. you are not allowed to rotate the magic squares.
Determine the minimum total cost to build the wall.
This problem has multiple test cases. The first line consists of an integer $T$ (1ドル ≤ T ≤ 20$), which represents the number of test cases.
Each test case consists of two lines. The first line consists of two integers $N$ $D$ (1ドル ≤ N ≤ 10,円 000$; 1ドル ≤ D ≤ 10^7$). The second line consists of $N$ integers $C_i$ (1ドル ≤ C_i ≤ 10,円 000$).
For each test case, output an integer in a single line representing the minimum total cost to build the wall.
3 3 5 500 1000 100 1 4 30 4 4 30 30 30 30
2100 480 120
For the first test case, set the length of the side of magic square 1ドル,ドル 2ドル$ and 3ドル$ to 1ドル,ドル 0ドル,ドル and 4ドル,ドル respectively. The total cost to build the wall is 1ドル^2 \cdot 500 + 0^2 \cdot 1000 + 4^2 \cdot 100 = 2100,ドル which can be shown to be the minimum.
For the second test case, the only solution is to set the length of the side of magic square 1ドル$ to 4ドル$. The total cost to build the wall is 4ドル^2 \cdot 30 = 480$.
For the third test case, set the length of the side of all magic squares to 1ドル$. The total cost to build the wall is 120ドル,ドル which can be shown to be the minimum.
3 10 20 1 2 3 4 5 6 7 8 9 10 10 100 1 2 3 4 5 6 7 8 9 10 1 10000000 10000
140 3419 1000000000000000000
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2023 K번