問題一覧 > 通常問題

No.1060 素敵な宝箱

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 109
作問者 : Enjapma_kyoproEnjapma_kyopro / テスター : okuraofvegetablokuraofvegetabl
49 ProblemId : 4274 / 出題時の順位表
問題文最終更新日: 2020-05-22 20:37:55

問題文

あなたと Enjapma 君は、 $2$ 人でゲームをすることにしました。
ゲームのルールは次の通りです。

  • $1$ . 机の上に $N$ 個の宝箱が置かれている。$N$ は偶数である。宝箱は初め、全て閉じている。
  • $2$ . 宝箱の中には宝石がいくつか入っている。宝石には、種類が $M$ 種類あり、$i$ 番目の宝箱には、 $j$ 種類目の宝石が $A_{ij}$ 個入っている。
  • $3$ . ゲームは先攻と後攻に分かれて行う。あなたが先攻で、Enjapma 君が後攻である。
  • $4$ . 先攻と後攻が交互に、閉じている宝箱を $1$ つ選んで開け、中の宝石を全て獲得する。以後、閉じている宝箱がなくなるまでこれを繰り返す。
  • $5$ . 両プレイヤーそれぞれの得点は、獲得した $j$ 種類目の宝石の数を $C_j$ 個として、 ${C_1}^2 + {C_2}^2 + {C_3}^2 + ... + {C_M}^2$ で表される。

ゲーム終了時のあなたの得点を $X$ 、Enjapma 君の得点を $Y$ とします。
あなたが $X - Y$ の値を最大化、Enjapma 君が $X-Y$ の値を最小化するために最適な戦略を取った場合、最終的な $X-Y$ の値はいくつになるでしょう?
なお、解の値の絶対値が $10^{18}$ を超えないことが、この制約下で証明できます。

入力

$N\ M$
$A_{11}\ A_{12}\ \dots\ A_{1M}$
$A_{21}\ A_{22}\ \dots\ A_{2M}$
$\vdots$
$A_{N1}\ A_{N2}\ \dots\ A_{NM}$

  • 入力はすべて整数
  • $N$ は偶数
  • $2 \le N \le 300$
  • $1 \le M \le 300$
  • $0 \le A_{ij} \le 100$

出力

あなたが $X - Y$ の値を最大化、Enjapma 君が $X-Y$ の値を最小化する戦略を取った場合の、$X-Y$ の値を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4 3
1 2 0
2 0 1
1 1 0
0 0 1
出力
5

あなたが $1$ 番目の宝箱を開けて、Enjapma 君が $2$ 番目の宝箱を開けます。
次に、あなたが $3$ 番目の宝箱を開けて、Enjapma 君が $4$ 番目の宝箱を開けます。
あなたの得点は、 $2^2 + 3^2 + 0^2 = 13$ で、$13$ 点です。
Enjapma 君の得点は、$2^2 + 0^2 + 2^2 = 8$ で、$8$ 点です。

サンプル2
入力
2 4
2 0 2 0
0 5 2 2
出力
25

あなたが $2$ 番目の宝箱を開けて、 Enjapma 君が $1$ 番目の宝箱を開けます。
あなたの得点は、 $0^2 + 5^2 + 2^2 + 2^2 = 33$ で、$33$ 点です。
Enjapma 君の得点は、$2^2 + 0^2 + 2^2 + 0^2 = 8$ で、$8$ 点です。

サンプル3
入力
4 3
0 0 0
0 0 0
0 0 0
0 0 0
出力
0

全ての宝箱は空箱でした。

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