問題一覧 > 通常問題

No.1199 お菓子配り-2

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 180
作問者 : PCTprobabilityPCTprobability / テスター : 57tggx57tggx
4 ProblemId : 4774 / 出題時の順位表
問題文最終更新日: 2020-08-28 23:42:49

問題文

本当に申し訳ありません。$1$ ケース行の末尾に半角スペースが入っていました。 $ N $ 個のお菓子と、$ M $ 人の子供がいます。お菓子にはそれぞれ $ 1, 2, \ldots, N $ の番号が、子供にはそれぞれ $ 1, 2, \ldots, M $ の番号がついています。 子供にはそれぞれ幸せ度が存在し, 初めは全ての子供の幸せ度が $ 0 $ です。

今から子供たちは、 $ 1, 2, \ldots, N $ 番目のお菓子について順番に食べるか食べないかを選択していきます。このとき、 $ M $ 人の子供たちは全て同じ選択をします。つまりある子供が $ i $ 番目のお菓子を食べると、他の子供もみな $ i $ 番目のお菓子を食べます。

お菓子 $ i $ を子供 $ j $ が食べると、それが奇数個目に食べたお菓子であれば幸せ度が $ A_{i, j} $ 増加しますが、偶数個目に食べたお菓子であれば幸せ度が $ A_{i, j} $ 減少します。

子供たちがそれぞれのお菓子について適切に食べるか食べないか選択していったとき、最終的な幸せ度の合計の最大値を求めてください。 21:35 出力内容を修正しました(幸福度→幸せ度)

入力

$N\ M$
$A_{1,1}\ A_{1,2}\ \ldots\ A_{1,M}$
$A_{2,1}\ A_{2,2}\ \ldots\ A_{2,M}$
$\ldots$
$A_{N,1}\ A_{N,2}\ \ldots\ A_{N,M}$

  • 入力は全て整数である。
  • $1 \le N,M \le 1000=10^3$
  • $1 \le A_{i,j} \le 10^{10}$

出力

あり得る幸せ度の合計値の内最大値を出力して最後に改行してください。

サンプル

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

最後のお菓子のみを選ぶのが適切です。

サンプル2
入力
1 1
4
出力
4

サンプル3
入力
5 3
3 5 4
74 6 23
234 45 23
76 3 1212
466 3 1
出力
1291

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