← 返回题目列表

Codeforces · 243/D

D. 立方体

中文机器翻译题面 查看原题

有一天,Petya 从他妈妈那里得到了一套木立方体作为礼物。佩蒂亚立即用这些立方体建造了一座完整的城市。

城市的基地是一个n×n的正方形,分为单位正方形。正方形的边与坐标轴平行,正方形的对角坐标为 (0, 0) 和 (n, n)。佩蒂亚在每个单位方块上建造了一座木制立方体塔。木立方体的边也有单位长度。

之后,Petya 离开他的杰作无限大的距离,沿着向量 v = (vx, vy, 0) 的方向观察它。彼佳想知道,从这个位置可以看到多少个不同的立方体。帮他找到这个号码。

每个立方体都包含边框。我们认为,如果有一条射线从属于立方体的某个点 p 发出,沿向量 - v 的方向(不包含属于其他立方体的任何点),则立方体是可见的。

输入

第一行包含三个整数 n、vx 和 vy(1 ≤ n ≤ 103、|vx|、|vy| ≤ |104|、|vx| + |vy| > 0)。

接下来的 n 行每行包含 n 个整数:第 i 行中的第 j 个整数 aij (0 ≤ aij ≤ 109, 1 ≤ i, j ≤ n) 表示位于单位正方形上的立方体塔的高度,该立方体塔的对角点为 (i - 1, j - 1) 和 (i, j)。

输出

打印一个整数——可见立方体的数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

5 -1 2
5 0 0 0 1
0 0 0 0 2
0 0 0 1 2
0 0 0 0 2
2 2 2 2 3

输出 #1

20

输入 #2

5 1 -2
5 0 0 0 1
0 0 0 0 2
0 0 0 1 2
0 0 0 0 2
2 2 2 2 3

输出 #2

15