問題一覧 > 通常問題

No.2094 Symmetry

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : AngrySadEightAngrySadEight / テスター : taiga0629kyoprotaiga0629kyopro
4 ProblemId : 8585 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-07 09:33:25

問題文

$2N$ 行 $2N$ 列のマス目があり,どのマスも白か黒の色で塗られています.このマス目の $i$ 行 $j$ 列目のマスのことを,マス $(i,j)$ と表します.

最初,$S_{i,j}=$ # ならばマス $(i,j)$ が黒で塗られており,$S_{i,j}=$ .ならばマス $(i,j)$ が白で塗られています.

マス目に対して,次の状態が満たされているとき,マス目はシンメトリーであると言います.

  • マス目を左右反転させたものと,もとのマス目に対して,全てのマスの色が等しい.
  • 厳密には,$1 \leq i \leq 2N, 1 \leq j \leq 2N$ を満たすすべての $i,j$ に対して,マス$(i, j)$ とマス $(i, 2N + 1 - j)$ の色は等しい.

はちじくんは,このマス目に対して,次のような操作を $0$ 回以上の何回でも行うことができます.

  • 白で塗られたマスと,黒で塗られたマスを,一つずつ選ぶ.白で塗られていた方のマスの色を黒に,黒で塗られていた方のマスの色を白に変える.

マス目がなるべく整っているべきだと思っているはちじくんは,マス目の綺麗さを最大化したいです.マス目の綺麗さは次のように計算されます.

  • 黒で塗られているようなマス $(i,j)$ すべてに対して, $C_{i,j}$ を足し合わせた値が,マス目の綺麗さである.
  • ただし,それに加えて,マス目がシンメトリーであるならば,マス目の綺麗さは $K$ 増加する.

達成可能な綺麗さの最大値を求めてください.

入力

$N$ $K$
$S_1$
$S_2$
$\vdots$
$S_{2N}$
$C_{1,1}$ $C_{1,2}$ $\cdots$ $C_{1,2N}$
$C_{2,1}$ $C_{2,2}$ $\cdots$ $C_{2,2N}$
$\vdots$
$C_{2N,1}$ $C_{2N,2}$ $\cdots$ $C_{2N,2N}$

  • $N, K, C_{i,j}$ は整数である.
  • $1 \leq N \leq 250$
  • $0 \leq K \leq 10^{14}$
  • $S_{i}$ は #. からなる長さ $2N$ の文字列である.
  • $-10^9 \leq C_{i,j} \leq 10^9$

出力

答えを出力せよ.

サンプル

サンプル1
入力
1 22
#.
.#
13 41
39 8
出力
80

次のように操作を行うのが最適です.

  • マス $(1,1)$ とマス $(1,2)$ を選んで操作する.マス $(1,1)$ の色は白に,マス $(1,2)$ の色は黒になる.
  • マス $(2,1)$ とマス $(2,2)$ を選んで操作する.マス $(2,1)$ の色は黒に,マス $(2,2)$ の色は白になる.

このとき,マス目はシンメトリーでないため,綺麗さの値は $41+39=80$ となります.綺麗さの値をこれより大きくすることはできません.

サンプル2
入力
1 39
#.
.#
13 41
39 8
出力
93

次のように操作を行うのが最適です.

  • マス $(1,2)$ とマス $(2,2)$ を選んで操作する.マス $(1,2)$ の色は黒に,マス $(2,2)$ の色は白になる.

このとき,マス目はシンメトリーであるため,綺麗さの値は $13+41+39=93$ となります.綺麗さの値をこれより大きくすることはできません.

サンプル3
入力
1 1000000000
##
##
-1000000000 -1000000000
-1000000000 -1000000000
出力
-3000000000

綺麗さの値は負になることもあります.

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