#P18792. [Omi2018] 墨西哥城地图

[Omi2018] 墨西哥城地图

[Omi2018] 墨西哥城地图

题目描述

一张地图被划分为 NN 行、MM 列的方格,每个格子上有一个字符 0 或 1。1 表示一个可以游览的地点,0 表示普通格子。

你希望从地图中截取一个非空的矩形子地图,使其中恰好包含 KK 个可以游览的地点。

请计算满足条件的矩形子地图有多少个。矩形的四条边均沿方格边界;只要包含的格子集合不同,就视为不同矩形。

输入格式

第一行包含三个整数 N,M,KN,M,K。

接下来 NN 行,每行包含一个长度为 MM 的 01 字符串,表示地图。

输出格式

输出一个整数,表示包含恰好 KK 个 1 的非空矩形数量。

答案可能超过 32 位有符号整数的范围。

样例输入

3 3 2
101
000
101

样例输出

8

数据范围

  • 1≤N,M≤15001\le N,M\le1500;
  • 0≤K≤60\le K\le6。

其中,20 分的数据满足 N,M≤20N,M\le20,其余 80 分没有额外限制。