#10946. 面积不超过k的子矩形个数

内存限制:256 MiB 时间限制:1000 ms 输入文件: mian.in 输出文件: mian.out
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

给定一个由n*m个单元格子组成的矩形,每个格子的边长为1,请计算面积不超过k的所有子矩形的个数。

例如:2*3的矩形,假设k=2

则共有13个面积不超过k的子矩形,其中:

1×1的正方形,面积为1,有6个;

2×1的长方形,面积为2,有4个;

1×2的长方形,面积为2,有3个。

输入格式

一行,三个数,第一个是n,第二个m,第三个k

输出格式

符合条件子矩形个数

样例

输入

2 3 2

输出

13

数据范围与提示

80%数据: 1<=n,m<=100

100%数据: 1<=n,m<=500 1<=k<=n*m