A61936.小明的斜线总和

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小明又获得了一个 nnmm 列的二维矩阵,他已经很熟悉如何去求矩阵中行的总和以及列的总和了, 因此这一次他想试一试求斜线上的总和。

对于矩阵中所有的斜线(从左上往右下的斜线), 求斜线上数字总和的最大值。

输入格式

第一行给定两个整数 nnmm, 代表矩阵的大小为 nnmm(1n,m1000)(1 \le n, m \le 1000)

接下来 nn 行, 每行 mm 个数字, 代表该二维矩阵的数值。(1000aij1000)(-1000 \le a_{ij} \le 1000)

输出格式

输出一个整数, 代表斜线上数字的最大总和是多少。

输入输出样例

  • 输入#1

    3 4
    -4 1 -3 5
    -3 -2 -3 5
    1 -1 0 -5

    输出#1

    5

说明/提示

样例解释:

按照左上到右下的斜线,可以将矩阵划分成上图所示的几条不同斜线,斜线之间使用不同的颜色区分,分别计算每条斜线的总和并且求取最大值即可。

首页