問題一覧 > 通常問題

No.1199 Candy Distribution - 2

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 249
作問者 : PCTprobability / テスター : 57tggx
お気に入りにしたユーザー ProblemId : 4774 / 自分の提出
問題文最終更新日: 2020-08-28 23:42:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 263 (順位表) の他の問題:

Problem Statement

We are truly sorry. In $1$ case, there was a trailing half-width space at the end of a line. There are $ N $ candies and $ M $ children. The candies are numbered $ 1, 2, \ldots, N $, and the children are numbered $ 1, 2, \ldots, M $. Each child has a happiness value, and initially the happiness of every child is $ 0 $.

The children will now choose whether or not to eat each candy, in the order $ 1, 2, \ldots, N $. All $ M $ children make the same choice. That is, if one child eats candy $ i $, all the other children also eat candy $ i $.

When child $ j $ eats candy $ i $, if it is an odd-numbered candy among those eaten, the child's happiness increases by $ A_{i, j} $; if it is an even-numbered candy among those eaten, the child's happiness decreases by $ A_{i, j} $.

Find the maximum possible final total of the children's happiness when they choose appropriately whether or not to eat each candy. 21:35 Corrected the output description (幸福度 → 幸せ度, both meaning "happiness").

Input

$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}$

  • All inputs are integers.
  • $1 \le N,M \le 1000=10^3$
  • $1 \le A_{i,j} \le 10^{10}$

Output

Output the maximum possible total happiness, followed by a newline.

Sample

Sample 1
Input
4 3
1 2 3
2 3 4
3 4 5
4 5 6
Output
15

It is optimal to choose only the last candy.

Sample 2
Input
1 1
4
Output
4

Sample 3
Input
5 3
3 5 4
74 6 23
234 45 23
76 3 1212
466 3 1
Output
1291

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