← 返回题目列表

AtCoder · codefestival_2016_qualA_d

D. 网格和整数

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

分数: 800 点

问题陈述

有一个网格 R 行和 C 列。 我们称该单元格为 r第行和 c- 第列 (r,c).

高桥先生将非负整数写入 N 的单元格,即他写了一个非负整数 a_i 进入 (r_i,c_i)对于每个 i (1≤i≤N)。 之后他就睡着了。

青木先生找到了网格,并试图通过将整数写入所有剩余单元格来给高桥先生带来惊喜。 网格必须满足以下条件才能真正让高桥先生感到惊讶。

  • 状况 1:每个单元格包含一个非负整数。
  • 状况 2:对于任何 2×2 由网格上的单元格形成的正方形,左上角和右下角整数之和必须始终等于右上角和左下角整数之和。

确定是否可以通过将整数正确写入所有剩余单元格来满足这些条件。

约束

  • 2≤R,C≤10^5
  • 1≤N≤10^5
  • 1≤r_i≤R
  • 1≤c_i≤C
  • (r_i,c_i) ≠ (r_j,c_j) (i≠j)
  • a_i 是一个整数。
  • 0≤a_i≤10^9

输入

输入由标准输入按以下格式给出:

R C
N
r_1 c_1 a_1
r_2 c_2 a_2
:
r_N c_N a_N

输出

打印 Yes 如果可以通过将整数正确写入所有剩余单元格来满足条件。 否则,打印 No.


示例输入 1

2 2
3
1 1 0
1 2 10
2 1 20

示例输出 1

Yes

您可以按如下方式编写整数。


示例输入 2

2 3
5
1 1 0
1 2 10
1 3 20
2 1 30
2 3 40

示例输出 2

No

有两个 网格上的 2×2 正方形,由以下单元格组成:

  • 细胞 (1,1), (1,2), (2,1) 和 (2,2)
  • 细胞 (1,2), (1,3), (2,2) 和 (2,3)

你必须写 40 进入空单元格以满足左侧方块的条件,但不满足右侧方块的条件。


示例输入 3

2 2
3
1 1 20
1 2 10
2 1 0

示例输出 3

No

你必须写 -10 进入空单元格以满足条件 2,但它不满足条件 1.


示例输入 4

3 3
4
1 1 0
1 3 10
3 1 10
3 3 20

示例输出 4

Yes

您可以按如下方式编写整数。


示例输入 5

2 2
4
1 1 0
1 2 10
2 1 30
2 2 20

示例输出 5

No

所有单元格均已包含整数和条件 2 不满意。