No.1199 Candy Distribution - 2
タグ : / 解いたユーザー数 249
作問者 :
PCTprobability
/ テスター :
57tggx
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もしくは右上の雲マークをクリックしてアカウントを作成してください。