시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 (추가 시간 없음) | 512 MB | 27 | 3 | 3 | 15.000% |
Note that $0$-based indexing is used throughout the problem.
You are given an array $a$ of length $n$ and $k$ non-empty sets of integers from $0$ to $n-1$. Let $S_p$ denote the $p$-th set. Each integer from $0$ to $n-1$ belongs to exactly one of those sets. It is guaranteed that $0$ belongs to $S_0$.
You choose a \uline{nonincreasing} array $c$ of nonnegative reals. $c_0$ must be positive. Let $d_p$ denote $\sum_{i \in S_p} c_i a_i$. Let $X$ denote $\frac{\min_{p=1}^{k-1} d_p}{d_0}$. What is the maximum value of $X$ you can obtain by choosing $c$ accordingly?
The first line contains two integers $n$ and $k$ ($2 \leq n \leq 4 \cdot 10^4, 2 \leq k \leq 4$), the length of $a$ and the number of sets.
The second line contains $n$ integers $a_i$ ($1 \leq a_i \leq 10^9$), the elements of $a$.
The third line contains $n$ integers $b_i$ ($b_0 = 0, 0 \leq b_i < k$) meaning that $i$ belongs to $S_{b_i}$.
All sets $S_p$ are non-empty. In other words, all integers from $0$ to $k-1$ occur at least once among $b_i$.
Print a single integer --- the maximum value of $X$ you can obtain accurate to absolute or relative error of at most $10^{-4}$.
4 4 1 1 1 1 0 1 2 3
1
3 3 3 2 2 0 1 2
0.66666666666666666668
5 4 3 2 1 2 5 0 1 3 0 2
0.29411764686215561816