跳到主要内容
图灵 OJTURING / ONLINE JUDGE

C. [HNOI2003] 激光炸弹

  • 传统题
  • 2000ms
  • 512MiB

[HNOI2003] 激光炸弹

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

地图上有 nn 个目标,目标 ii 位于整数坐标 (xi,yi)(x_i,y_i),价值为 viv_i。一颗炸弹覆盖一个边长为 mm、边与坐标轴平行的正方形,严格位于正方形内部的目标会被摧毁,边界上的目标不受影响。投放位置可以自由选择,并非只能取整。求一颗炸弹能摧毁的目标价值之和的最大值。

同一坐标可能有多个目标,它们的价值分别计入。

输入格式

第一行输入 n,mn,m。接下来 nn 行,每行输入 xi,yi,vix_i,y_i,v_i。

输出格式

输出一个正整数,表示最大价值之和。

数据范围

1≤n≤1041\le n\le10^4;1≤m≤50001\le m\le5000;0≤xi,yi≤50000\le x_i,y_i\le5000;1≤vi<1001\le v_i<100。保证答案不超过 3276732767。

样例

3 2
0 0 3
1 1 4
2 2 8
12

来源

洛谷 P2280。题意按原题整理,保留原题署名;测试数据由本站独立构造。

前缀和与差分

未参加
状态
已结束
规则
XCPC
题目
6
开始于
2026-10-28 18:00
结束于
2026-10-28 23:00
持续时间
5 小时
主持人
参赛人数
17