[语言月赛 202405] 最大的和

Luogu

IDLGB3975

Time1000ms

Memory128MB

DifficultyP2

模拟2024O2优化循环结构数组语言月赛

小 S 喜欢连在一起的数字，如果这些数字的和很大就更好了。所以她现在要给你一个 $n$ 行 $n$ 列的网格 $A$，第 $i$ 行第 $j$ 列上填有一个**整数** $A_{i, j}$。接下来你可以在 $A$ 上任取**一行**、**一列**或**一条与任意对角线平行**且**只经过网格交叉点**的**直线**（注意，不是线段），满足经过至少一个数字，且经过的数字之和最大。如果对上面的表述有疑惑，请参考**样例解释**辅助理解。你需要告诉小 S 这个最大的数字之和。 ## Input 输入共 $n+1$ 行。第一行，一个正整数 $n$，表示方阵的行数、列数。接下来 $n$ 行，每行 $n$ 个用空格隔开的**整数**，其中第 $i$ 行第 $j$ 个整数表示 $A_{i, j}$。 ## Output 输出一行一个整数，表示最大的数字之和。 [samples] ## Note ### 样例 1 解释对于样例 $1$，不难看出第 $3$ 行数字之和最大，有 $3 + 3 + 3 = 9$。 ### 样例 2 解释对于样例 $2$，数字之和最大的，满足条件的线如下所示： ![](https://cdn.luogu.com.cn/upload/image_hosting/3srzjj2n.png?x-oss-process=image) 此时有 $4 + 9 = 13$。注意，因为要求与对角线平行的直线只能经过**网格交点**，所以并不能出现同时取 $4, 1, 9$ 或同时取 $4, 1, 9, 2$ 这样的情况。 ### 样例 $3$ 解释取某条只经过一个 $-1$ 的直线即为最大。注意，不可以一个数字都不选。 ### 样例 $4$ 解释显然，取斜着的线一定不优，只能选择中间那一行或一列，答案是 $-10 + 99999 - 10 = 99979$。 ### 数据范围对于前 $30 \%$ 的数据，保证 $A_{1, 1}$ 或 $A_{n, n}$ 的值为网格中**唯一的**非负整数。对于另 $20 \%$ 的数据，保证**每一行**数字相同，且最后一行中的数字之和为**最大值**。对于另 $20 \%$ 的数据，保证**每一行**数字相同，网格中不存在负数。对于 $100 \%$ 的数据，保证 $1 \leq n \leq 2 \times 10^3, -10^5 \leq A_{i, j} \leq 10^5$。

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

3
-1 -1 -1
-1 -1 -1
-1 -1 -1

Output #3

-1

Input #4

3
-100 -10 -100
-10 99999 -10
-100 -10 -100

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛 202405] 最大的和",
    "description": {
      "content": "小 S 喜欢连在一起的数字，如果这些数字的和很大就更好了。 所以她现在要给你一个 $n$ 行 $n$ 列的网格 $A$，第 $i$ 行第 $j$ 列上填有一个**整数** $A_{i, j}$。 接下来你可以在 $A$ 上任取**一行**、**一列**或**一条与任意对角线平行**且**只经过网格交叉点**的**直线**（注意，不是线段），满足经过至少一个数字，且经过的数字之和最大。 如果对",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3975"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 S 喜欢连在一起的数字，如果这些数字的和很大就更好了。\n\n所以她现在要给你一个 $n$ 行 $n$ 列的网格 $A$，第 $i$ 行第 $j$ 列上填有一个**整数** $A_{i, j}$。\n\n接下来你可以在 $A$ 上任取**一行**、**一列**或**一条与任意对角线平行**且**只经过网格交叉点**的**直线**（注意，不是线段），满足经过至少一个数字，且经过的数字之和最大。\n\n如果对...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments