/ Vijos / 题库 /

圆和点

圆和点

描述

平面上有M*N个点
排列成N行M列的方阵,每两个相邻的点之间距离是1
并且平面上有K个圆,它们的圆心都在那些点上
对于每个圆Ci,它会使在其内部或在其上的点(L<=Ri)得到Bi点权值

试求权最大的点的权值和个数

1<=M<=30000
1<=N<=1000
1<=K<=1000
1<=Ri<=30000
1<=Bi<=1000

格式

输入格式

第一行一个自然数M
第二行一个自然数N
第三行一个自然数K
接下来K行,每行四个整数,表示圆心位置(第几行,第几列),半径,权值

输出格式

第一行一个整数,最大权值
第二行一个整数,具有最大权值的点的个数

样例1

样例输入1

3
5
3
1 3 2 5
3 1 2 7
5 1 1 5

样例输出1

12
5

限制

各个测试点5s

信息

ID
1528
难度
5
分类
数据结构 | 线段树组合数学 | 差分 点击显示
标签
(无)
递交数
320
已通过
100
通过率
31%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库