QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 128 MB 總分: 10

#6064. 博物馆 [A]

统计

著名窃贼 Bajtymon 想要洗劫拜特国国家博物馆。他特别觊觎陈列在博物馆最宏伟展厅中的皇室珠宝。该展厅内有 $n$ 件展品,由 $m$ 名守卫看守。博物馆馆长为了确保守卫不会过多干扰游客欣赏展品,要求他们始终站在指定位置并朝向同一个方向。

Bajtymon 获得了展厅的平面图,上面标明了展品和守卫的位置。他从一位相识的珠宝商那里获得了所有展品的估价,并得知了贿赂每名守卫所需的费用,以便在行窃时让他们对自己的行为视而不见。

Bajtymon 现在正在思考他能获得多大的收益。他希望选择贿赂一部分守卫,使得所有未被任何未受贿守卫监视的展品的总价值,减去贿赂所选守卫的总成本,达到最大化。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 200\,000$),分别表示展品的数量和守卫的数量。为了描述它们的位置,假设博物馆平面图上给定了一个直角坐标系。输入的第二行包含两个整数 $w$ 和 $h$ ($1 \le w, h \le 10^9$),描述守卫的视野范围。每名守卫都朝向 $y$ 坐标减小的方向观察,其视野张角的一半的正切值为 $w/h$。为简化起见,我们假设守卫和展品的大小可以忽略不计。守卫可以观察到其视野范围内的所有展品(包括边界上的),即使它们被其他展品或守卫遮挡。

接下来的 $n$ 行描述展品的位置;其中第 $i$ 行包含三个整数 $x_i, y_i, v_i$ ($-10^9 \le x_i, y_i \le 10^9, 1 \le v_i \le 10^9$),表示第 $i$ 件展品的价值为 $v_i$ 拜特币,位于坐标 $(x_i, y_i)$。接下来的 $m$ 行以类似的方式描述守卫的位置(其中 $v_i$ 表示 Bajtymon 为贿赂第 $i$ 名守卫所需支付的拜特币金额)。每个点上最多只能有一名守卫或一件展品。

输出格式

你的程序应输出一行,包含一个整数,表示 Bajtymon 可以获得的最大收益(以拜特币为单位)。

样例

输入 1

5 3
2 3
2 6 2
5 1 3
5 5 8
7 3 4
8 6 1
3 8 3
4 3 5
5 7 6

输出 1

6

说明 1

每名守卫的视野张角略大于 $67^\circ$。Bajtymon 应该贿赂两名守卫,支付 $3 + 6$ 拜特币,并拿走价值为 $2 + 8 + 4 + 1$ 拜特币的展品。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.