题目描述

给你一个 $n * m$ 的矩阵，每个元素为 $w_{i,j}$，从左下角的格子开始走，只能往右或者往上每次走一个。

从左下角的格子开始走，只能往右或者往上，每次走一个格子。

每个格子上都有一个数。

问怎么走才能使得最终经过的数值之和最大？

输入格式

输入三个整数 $n, m, seed$

矩阵中的元素 $w_{i,j}$ 由 $seed$ 随机产生。

输出格式

输出走到右上角的最大值。

输入输出样例

输入 #1

3 2 114514

输出 #1

2739225543

提示

矩阵内数值的生成

#include <iostream>
using namespace std;

struct Rnd {
    const long long kMod = 1e9 + 1;
    const long long kMul = 1103515245;
    const long long kInc = 13331;

    int seed;

    Rnd(int s) {
        seed = s;
    }

    int next_int() {
        seed = (kMul * seed + kInc) % kMod;
        return seed;
    }
};

int main() {
    Rnd rnd(114514);
    int mat[10][10];
    int row = 3, col = 2;

    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            mat[i][j] = rnd.next_int();
        }
    }

    return 0;
}

样例 1 解释

输入 3 2 114514 产生的矩阵为

$$\begin{pmatrix} 944652894 & 719943493 \\ 269595497 & 625362356 \\ 805033659 & 556277872 \end{pmatrix} $$

最优路径是 $(3,1) \to (2,1) \to (1,1) \to (1,2)$，

结果是 2739225543

数据范围

对于 $30\%$ 的数据 $1 \le n, m \le 10$；

对于 $100\%$ 的数据 $1 \le n, m \le 2000, 0 \le w_{i,j} \le 10^9, 0 \le seed \le 10^9$