TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8108
  • 题目
  • P8108棋盘谜题
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2s 256MB
    问题描述

    棋盘可以看成一个N*M 的网格。棋子可以摆放在任何一个格子里,而不是网格线的交叉点上。现将一个棋子放在了左上角的格子上,棋子只会向右或者向下移动。每个格子有一个权值,请问,从左上角到右下角的所有路径中:

    1.经过的格子的权值和最大是多少?

    2.权值和最大的路径一共有多少条?

    输入格式

    第一行两个整数N,M。 接下来N 行,每行M 个整数,表示每个格子的权值。

    Ai,j 表示第i 行第j 列格子的权值。

    30%的数据保证,N≤5,M≤5。

    60%的数据保证,N≤100,M≤100。

    另有20%的数据保证,对于任意的i 和j,Ai,j = 1。

    100%的数据保证,N≤2000,M≤2000,|Ai,j|≤10^9。

    输出格式

    输出两行,第一行表示最大权值和,第二行表示权值和最大的路径数除以 1e9+7 的余数。

    样例输入

    3 3
    1 1 1
    1 2 1
    1 1 1

    样例输出

    6
    4