1482. 棋盘上的士兵

时间限制 1000 ms   内存限制 128 MB

        在一个N行M列的棋盘上,摆放着K个士兵,一个士兵占据一个格子(可能有多个士兵占据同一个格子)。         第i个士兵控制棋盘上所有与它相距不超过Ri的格子。         两个格子(X1,Y1)、(X2,Y2)间的距离定义为|X1-X2|+|Y1-Y2|。         求所有被控制的格子的总数。

输入数据

&nbsp &nbsp &nbsp &nbsp 第一行三个正整数N,M,K。
&nbsp &nbsp &nbsp &nbsp 以下K行,每行三个整数Xi(1≤Xi≤N),Yi(1≤Yi≤M),0≤Ri≤10^8)。
其中Xi,Yi分别表示第i个士兵在第几行和在第几列。

输出数据

&nbsp &nbsp &nbsp &nbsp 在第一行输出所有被控制的格子的总数。

样例输入

复制
4 4 3
1 1 1
3 1 1
3 3 1
 · · \n
 · · \n
 · · \n
 · · \n

样例输出

复制
10
  \n

样例说明

&nbsp &nbsp &nbsp &nbsp 在15%的数据中,1≤N,M≤1000,1≤K≤100
&nbsp &nbsp &nbsp &nbsp 在25%的数据中,1≤N,M≤5000,1≤K≤100
&nbsp &nbsp &nbsp &nbsp 在35%的数据中,1≤N,M≤10000,1≤K≤100
&nbsp &nbsp &nbsp &nbsp 在50%的数据中,1≤N,M≤100000,1≤K≤100
&nbsp &nbsp &nbsp &nbsp 在65%的数据中,1≤N,M≤100000000,1≤K≤100
&nbsp &nbsp &nbsp &nbsp 在80%的数据中,1≤N,M≤100000000,1≤K≤1000
&nbsp &nbsp &nbsp &nbsp 在100%的数据中,1≤N,M≤100000000,1≤K≤100000

提交

请先 登录

Source

纪中联赛模拟题 BY  CQF

© 2024 FAQs Contact About