No.1912 Get together 2
タグ : / 解いたユーザー数 49
作問者 :
Problem Statement
There are $N$ slimes and $M$ boxes. The value of slime $i\ (1\le i \le N)$ is $V_i$. The slimes and boxes are numbered, and they are denoted as slime $i\ (1 \le i \le N)$ and box $j\ (1\le j \le M)$, respectively.
You will now put each of the $N$ slimes into exactly $1$ of the $M$ boxes (there may be boxes that do not contain even $1$ slime).
There is a compatibility between slimes and boxes, represented by a string $S_i$ of length $M$ consisting only of o and x.
If the $j$-th character of $S_i$ is o, slime $i$ can be put into box $j$; if it is x, it cannot.
Find the maximum possible value of $\displaystyle \sum_{j=1}^{M}($the sum of the values of the slimes in box $j$$)^2$.
Input
$N$ $M$ $V_1$ $V_2$ $\dots$ $V_N$ $S_1$ $S_2$ $\vdots$ $S_N$
- $1 \le N \le 10^5$
- $1 \le M \le 20$
- $1 \le V_i \le 10^4$
- $|S_i|=M$
- $S_i$ contains at least $1$
o - All values in the input (except $S_i$) are integers
Output
Print the answer.
End the output with a newline.
Sample
Sample 1
Input
3 3 3 4 5 ooo oox xox
Output
144
It is optimal to put all the slimes into box $2$.
Sample 2
Input
4 2 2 3 6 5 ox xo oo xo
Output
200
Only slime $3$ has a choice of box. In this case, putting it into box $2$ together with slimes $2,\ 4$ makes the above value $2^2+(3+6+5)^2=200$, which is optimal.
Sample 3
Input
13 6 404 386 221 993 1 708 468 832 20 879 704 589 311 xoxxxx xooxox oxxoxx xoooox ooxoox oxooxo xxxxoo xooxox ooooox xxooxo xxooxx xxoxox oxxxoo
Output
26942778
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。