問題一覧 > 通常問題

No.1912 Get together 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 44
作問者 : chineristACchineristAC / テスター : tokusakuraitokusakurai shotoyooshotoyoo
7 ProblemId : 6852 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-05 18:11:18

問題文

$N$ 匹のスライムと $M$ 個の箱があります。スライム $i\ (1\le i \le N)$ の価値は $V_i$ です。スライムおよび箱には番号が振られており、それぞれスライム $i\ (1 \le i \le N)$、 箱 $j\ (1\le j \le M)$ と表記します。

これから $N$ 匹の各スライムを $M$ 個の箱のいずれか $1$ つに入れます ($1$ 匹もスライムが入っていない箱が存在してもかまいません)。 スライムと箱の間には相性があり、これは長さ $M$ で o, x のみからなる文字列 $S_i$ で表されます。 $S_i$ の $j$ 文字目が o のとき、スライム $i$ を箱 $j$ に入れることができますが、x のときは入れることができません。

$\displaystyle \sum_{j=1}^{M}($箱 $j$ に入っているスライムの価値の総和$)^2$ が最大でいくつになるか求めてください。

入力

$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$ は o を $1$ 文字以上含む
  • 与えられる入力は（$S_i$ 以外）すべて整数

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 3
3 4 5
ooo
oox
xox
出力
144

すべてのスライムを箱 $2$ に入れるのが最適です。

サンプル2
入力
4 2
2 3 6 5
ox
xo
oo
xo
出力
200

スライム $3$ のみが入れる箱を選ぶことができます。この場合はスライム $2,\ 4$ と共に箱 $2$ に入れると上記の値は $2^2+(3+6+5)^2=200$ となり、最適です。

サンプル3
入力
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
出力
26942778

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。