← 返回比赛
已结束 GESP巅峰赛#19
← 上一题 下一题 →

A4812 | 登塔

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

Alice 来到了一座魔塔，这座魔塔共有 $n$ 层，每层有 $m$ 个房间。房间的编号从 1 开始，依次记为 $1, 2, \dots, m$ 。每个房间 $(i, j)$ 中都藏有一些宝藏，其中 $i$ 表示第 $i$ 层， $j$ 表示第 $j$ 号房间，宝藏的价值记为 $v_{i,j}$ 。

魔塔有以下规则：
1. 封印规则：如果在第 $i$ 层选择了第 $j$ 号房间，那么在第 $i + 1$ 层，第 $j$ 号房间会被封印，无法被选择。
2. 选择限制：在每一层，Alice 必须且只能从一个未被封印的房间中取出宝藏。
3. 前进条件：只有从当前层的某个房间取出宝藏后，通往下一层的道路才会开启，Alice 才能进入下一层。
4. 终止条件：Alice 可以随时从魔塔中退出。

现在问，Alice 可以在魔塔中获得的宝藏的最大价值是多少。

输入格式

第一行 ：输入两个整数 $n$ 和 $m$，分别表示魔塔的层数和每层的房间数。
（$1 \le n, m \le 2 \times 10^5 ， 1 \le n \times m \le 10^6$）

接下来的 $n$ 行 ：每行输入 $m$ 个整数 $v_{i,1}$ $v_{i,2}$ $\dots$ $v_{i,m}$ ,每个整数之间用空格隔开，表示第 $i$ 层每个房间的宝藏价值。
（$1 \le v_{i,j} \le 10^9$）

输出格式

输出一个整数代表着Alice可以获得的最大的价值

输入输出样例

输入 #1
2 2 
1 2 
2 1
输出 #1
4
输入 #2
2 2 
1 2 
1 2
输出 #2
3
C++ 编辑器
输入
输出