시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 16 | 6 | 6 | 37.500% |
In a restaurant, given $N$ menus, where the menus are represented by the strings $S^1, \dots , S^N$. Each string $S^i$ is associated with an array $A^i$ (of the same length) of joy levels. In this problem, you should choose a submenu defined by three integers $(i, j, k)$, where $i$ is the index of one of the menus, and $j, k$ specify a substring of this chosen menu.
We need to find the submenu of the highest quality, where the quality $Q$ is defined by the function:
$$Q(i, j, k) = \text{popularity}(S^i_{j,k}) \cdot A^i_k \cdot |S^i_{j,k}|$$
Can you find the submenu of the highest quality? Please output the corresponding highest quality of the function $Q$.
The first line of the input contains a single integer $T$ specifying the number of test cases.
Each test case begins with a line containing an integer $N$ ($1 \le N \le 10^5$) specifying the number of menus in the restaurant.
Then $N$ lines follow, the $i$th line contains a string $S^i$ representing the $i$th menu. All the menus are nonempty strings consisting of lowercase English letters, and the sum of their lengths will not exceed $10^5$ per test case.
Then $N$ lines follow, the $i$th line contains array $A^i$, in which Ai has the same length as string $S^i$ and ($0 \le A^i_k \le 10^9$). The values of each array are space-separated.
For each test case, print a single line containing an integer $Q$ representing the maximum quality corresponding to the best submenu $(i, j, k)$.
2 2 aabaa aa 0 0 0 0 100 0 1 4 bbbaa aa aab aax 0 0 0 0 100 0 0 0 0 0 0 0 0
500 600
The triples corresponding to the answers of the two given cases are $(1, 1, 5)$ and $(1, 4, 5)$.