AT_arc122_f.[ARC122F] Domination

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在二维平面上有 $N$ 个红色石子和 $M$ 个蓝色石子。第 $i$ 个红色石子位于坐标 $(RX_i, RY_i)$ ，第 $j$ 个蓝色石子位于坐标 $(BX_j, BY_j)$ 。同一坐标上可以有多个石子。

你可以无限次地选择一个蓝色石子并将其移动到任意坐标。将坐标为 $(x, y)$ 的蓝色石子移动到 $(x', y')$ 时，所需的代价为 $|x - x'| + |y - y'|$ 。

你的目标是使得以下条件成立：

对于所有 $1 \leq i \leq N$ ，第 $i$ 个红色石子的右上区域内至少存在 $K$ 个蓝色石子。更严格地说，满足 $RX_i \leq BX'_j$ 且 $RY_i \leq BY'_j$ 的 $1 \leq j \leq M$ 的个数不少于 $K$ 。其中 $(BX'_j, BY'_j)$ 表示第 $j$ 个蓝色石子操作后的坐标。

请你求出达成目标所需的总代价的最小值。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $K$ $RX_1$ $RY_1$ $RX_2$ $RY_2$ $\vdots$ $RX_N$ $RY_N$ $BX_1$ $BY_1$ $BX_2$ $BY_2$ $\vdots$ $BX_M$ $BY_M$

输出格式

请输出答案。

输入输出样例

输入#1
```
3 2 1
0 0
2 0
0 2
1 0
0 1
```
输出#1
```
2
```
输入#2
```
3 2 2
0 0
2 0
0 2
1 0
0 1
```
输出#2
```
6
```

输入#3

10 10 3
985971569 9592031
934345597 151698665
212173157 492617927
623299445 288193327
381549360 462770084
681791249 242910920
569404932 353061961
357882677 463919940
110389433 533715995
9639432 700209424
771167518 75925290
439954587 566974581
738467799 122646638
267815107 900808287
886340750 70087431
434010239 822484872
388269208 879859813
393002209 874330449
154134229 924857472
667626345 460737380

输出#3

1165266772

说明/提示

限制条件

$1 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq K \leq \min(M, 10)$
$0 \leq RX_i, RY_i, BX_j, BY_j \leq 10^9$
输入的所有值均为整数

样例解释 1

可以进行如下操作：

将第 $1$ 个蓝色石子移动到坐标 $(2, 0)$ ，代价为 $|1-2| + |0-0| = 1$ 。
将第 $2$ 个蓝色石子移动到坐标 $(0, 2)$ ，代价为 $|0-0| + |1-2| = 1$ 。

样例解释 2

可以进行如下操作：

将第 $1$ 个蓝色石子移动到坐标 $(2, 2)$ ，代价为 $|1-2| + |0-2| = 3$ 。
将第 $2$ 个蓝色石子移动到坐标 $(2, 2)$ ，代价为 $|0-2| + |1-2| = 3$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页