TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3638
  • 問題
  • P3638采蘑菇
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    最近,何老板玩一款名叫“采蘑菇”的有趣手机游戏。
    游戏地图由水平放置的n块砖(编号1到n)构成,每一秒钟,每块砖上会新长出一些蘑菇,蘑菇的生命时间只有1秒钟,1秒钟后蘑菇就消失了。游戏玩家操控的游戏角色“马里奥”一开始位于第k块砖上,每一秒钟,马里奥有三种移动方式可以选择:
    1.原地不动,并采摘该砖上的蘑菇;
    2.移动到左边一块砖,并采摘该砖上的蘑菇;
    3.移动到右边一块砖,并采摘该砖上的蘑菇;
    游戏一共持续t秒钟,问马里奥最多能采集到多少颗蘑菇。

    入力形式

    第一行,四个整数n,t,k,分别表示砖块的数量,游戏的持续时间和一开始马里奥所处的位置。
    接下来一个t*n的整数矩阵,其中第i行描述第i秒钟的情况,第i行第j个数表示第i秒第j块砖上长出的蘑菇数。

    出力形式

    一行,一个整数,表示能够采摘到的最多蘑菇数。

    サンプル入力

    样例输入1:
    4 3 2
    3 1 1 1
    2 1 1 1
    1 5 4 1

    样例输入2:
    5 3 3
    3 1 3 3 2 
    5 6 5 1 6 
    7 4 3 4 4 

    样例输入3:
    6 4 2
    3 7 1 3 1 5 
    4 2 6 6 3 6 
    2 2 2 4 7 7 
    2 7 6 2 4 6 

    サンプル出力

    样例输出1:
    10

    样例输出2:
    16

    样例输出3:
    23

    ヒント

    对于30%的数据 1<=n<=10, 1<=t<=5;
    对于100%的数据 1<=n<=100, 1<=t<=1000 ,1<=每块砖上长出的蘑菇数<=10000

    样例1说明:
    第一秒由2号砖移动到1号砖,采3颗蘑菇
    第二秒呆在1号砖不动,采2颗蘑菇
    第三秒由1号砖移动到2号砖,采5颗蘑菇