在台灣,發(領)紅包是個再平常不過的事情了。
快要過年了,小孩們這次非常期待領紅包,這樣就可以去買電腦,買玩具:)
不過厭倦單純發紅包的大人們,今年想出了一個特別的遊戲,讓小孩們在領紅包時也順便玩遊戲。
大人們設計了一個 $m\times n$ 矩陣,並且在矩陣的某一些格子放上紅包,並且每個紅包都有至少一塊錢ww
現在大人們跟小孩們會玩遊戲,且他們每一回合都有機會拿走矩陣上的紅包。
每一回合拿紅包的規則如下:
一、從大人們先開始拿。大人一次可以拿很多個紅包,而且在一回合中可以拿很多次。
大人們能拿取紅包是有條件的,如果大人要拿走第 $i$ 行第 $j$ 列的紅包,必須要滿足其中至少一個以下條件:
二、大人拿完紅包之後輪到小孩。小孩們可以派出一人拿矩陣中的一個紅包,且拿走的紅包沒有條件限制。
遊戲持續到紅包都拿完為止。
這個局勢顯然對小孩比較有利,所以當大人們可以拿走紅包的時候,有能拿的紅包就會拿,不會留情的。
小明是其中一個小孩,他的超能力是透視眼,可以直接看穿每個紅包裡有多少錢。
可惜小孩們的數學都不好,需要你的求助,請寫個程式幫小孩們拿到盡可能多的錢。
第一行有 $n,m$ $(1\leq n,m \leq 10^3)$,表示矩陣的大小。
接下來有 $n$ 行,每一行有 $m$ 個數字,代表大人們安排的矩陣。
第 $i$ 行第 $j$ 列的紅包有數字 $A_i$ $(0\leq A_i \leq 10^3)$ ,如果 $A_i$ 是 $0$ 代表該位置沒有紅包,反之該位置就有 $A_i$ 元的紅包。
輸出一個數字,代表小孩最多可以拿多少錢。
在 Sample 1 中,因為第二直行只有一個紅包,大人們可以先把它拿走。然後輪到小孩。
小孩只能拿一個,所以選最大的 $9$,然後紅包在下一回合中被大人拿光。
貪心的大人們(X
No. | Testdata Range | Score |
---|---|---|
1 | 0~23 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 |