P3400 仓鼠窝

    • 49通过
    • 324提交
  • 题目提供者Created_equal1 管理员
  • 标签 单调队列 洛谷原创 高性能
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    萌萌哒的Created equal是一只小仓鼠,小仓鼠自然有仓鼠窝啦。

    仓鼠窝是一个由n*m个格子组成的行数为n、列数为m的矩阵。小仓鼠现在想要知道,这个矩阵中有多少个子矩阵!(实际上就是有多少个子长方形嘛。)比如说有一个2*3的矩阵,那么1*1的子矩阵有6个,1*2的子矩阵有4个,1*3的子矩阵有2个,2*1的子矩阵有3个,2*2的子矩阵有2个,2*3的子矩阵有1个,所以子矩阵共有6+4+2+3+2+1=18个。

    可是仓鼠窝中有的格子被破坏了。现在小仓鼠想要知道,有多少个内部不含被破坏的格子的子矩阵!

    输入输出格式

    输入格式:

    第一行两个正整数n和m,分别表示仓鼠窝的行数n、列数m。

    接下来n行,每行m个数,每个数代表对应的格子,非0即1。若为0,表示这个格子被破坏;反之代表这个格子是完好无损的。

    输出格式:

    仅一个正整数,表示未被破坏的子矩阵的个数。

    输入输出样例

    输入样例#1: 复制
    3 4
    1 1 1 1
    1 0 1 1
    1 1 0 1
    输出样例#1: 复制
    26

    说明

    __本题时限2s,内存限制256M,因新评测机速度较为接近NOIP评测机速度,请注意常数问题带来的影响。__

    No    n=    m=    备注
    1    2    2    无
    2    3    3    无
    3    5    5    无
    4    10    10    无
    5    2000    2000    所有格子均未被破坏
    6    3000    3000    所有格子均未被破坏
    7    2500    3000    有且仅有一个格子被破坏
    8    3000    2500    有且仅有一个格子被破坏
    9    200    200    无
    10    500    500    无
    11    500    500    无
    12    500    500    无
    13    1000    1000    无
    14    1000    1000    无
    15    1000    1500    无
    16    2500    2500    无
    17    2500    3000    无
    18    3000    2500    无
    19    3000    3000    无
    20    3000    3000    无
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。