시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.6 초 | 1024 MB | 244 | 50 | 39 | 23.780% |
Republic of JOI consists of $N$ states, numbered from $1$ to $N$. In 2022, the presidential election will be held in Republic of JOI. The election will be held in each state. The winner of the election in a state will get the vote of the state.
Rie will run for the president. She is planning to win the election. Her plan is to deliver a speech in order to increase the degree of reliability. After she delivers a speech, the following will happen.
A collaborator from State $i$ ($1 ≤ i ≤ N$) may deliver a speech outside State $i$. More than one person may deliver a speech in the same state simultaneously. For example, if two people deliver a speech in a state for $x$ hours, the total time of speech in the state will be increased by $2x$ hours. The time of speech needs not be an integer. We will ignore the travel time between states.
Since the election day is coming soon, Rie would like to get $K$ votes as soon as possible.
Given the number of the states and information of each state, write a program which calculate the minimum number of hours required to get $K$ votes.
Read the following data from the standard input. Given values are all integers.
$\begin{align*} & N \\ & K \\ & A_1 \, B_1 \\ & A_2 \, B_2 \\ & \vdots \\ & A_N \, B_N \end{align*}$
Write one line to the standard output. The output should contain the minimum number of hours required to get $K$ votes. Your solution will be judged correct if the absolute value of the difference from correct answer is less than or equal to $0.01$. The output should be written in one of the following formats.
123
, 0
, -2022
)123.4
, -123.00
, 0.00288
)The output should not be written in exponential notation. For example, 1.23456e+05
and 1.23456e5
are not allowed.
번호 | 배점 | 제한 |
---|---|---|
1 | 5 | $B_i = -1$ ($1 ≤ i ≤ N$). |
2 | 5 | $B_i = -1$ or $B_i = A_i$ ($1 ≤ i ≤ N$). |
3 | 11 | $N ≤ 7$. |
4 | 12 | $N ≤ 20$. |
5 | 33 | $N ≤ 100$. |
6 | 11 | $K = N$. |
7 | 23 | No additional constraints. |
3 3 1 5 2 3 4 5
5.500000000000000
If the election campaign is held in the following order, Rie will get the vote of every state in $5.5$ hours.
This sample input satisfies the constraints of Subtasks 3, 4, 5, 6, 7.
7 4 4 -1 11 -1 6 -1 12 -1 36 -1 11 -1 20 -1
32.000000000000000
If the election campaign is held in the following order, Rie will get $4$ votes in $32$ hours.
This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 5, 7.
5 3 4 -1 5 -1 6 -1 7 7 8 8
11.500000000000000
If the election campaign is held in the following order, Rie will get $3$ votes in $11.5$ hours.
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 7.
7 5 28 36 11 57 20 35 19 27 31 33 25 56 38 51
62.166666666666664
This sample input satisfies the constraints of Subtasks 3, 4, 5, 7.
20 14 106 277 175 217 170 227 164 245 118 254 139 261 142 270 185 200 162 241 153 239 128 264 103 299 147 248 158 236 160 232 183 205 194 197 135 260 153 234 128 260
644.203571428571422
This sample input satisfies the constraints of Subtasks 4, 5, 7.