AT_arc032_4.[ARC032D] アットコーダーモンスターズ

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

アットコーダーモンスターズ是一款组建怪兽队伍进行战斗的游戏。

你现在在一家出售怪兽的商店里。在这家商店中，有 $N$ 只怪兽排成一行。每只怪兽 $A_i\ (1\leq i\leq N)$ 都有如下两项能力值：

怪兽 $M_i$ 的攻击能力值 ${M_i}_{ATK}$
怪兽 $M_i$ 的防御能力值 ${M_i}_{DEF}$

现在，你打算从这 $N$ 只怪兽中选出恰好 $K$ 只不同的怪兽购买，并用它们组建队伍。然而，如果队伍中某项能力值相差太大的怪兽同时存在，队伍就会变得不稳定，因此你希望组建一个尽可能稳定的队伍。

更严格地说，对于队伍中任意两只怪兽 $X$ 和 $Y$ ，定义它们之间的不稳定度 $S_{X,Y}$ 为：

$S_{X,Y} = \max\{ |X_{ATK} - Y_{ATK}|, |X_{DEF} - Y_{DEF}| \}$

队伍的不稳定度为队伍中所有怪兽两两之间不稳定度的最大值。当队伍中只有一只怪兽时，队伍的不稳定度为 $0$ 。

你希望购买 $K$ 只怪兽，使得组建的队伍不稳定度最小。同时，你还想知道能够达到最小不稳定度的选法有多少种。

你需要输出能够达到的最小队伍不稳定度，以及达到该不稳定度的选法数对 $1,000,000,007$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$
${M_1}_{ATK}$ ${M_1}_{DEF}$
${M_2}_{ATK}$ ${M_2}_{DEF}$
$\vdots$
${M_N}_{ATK}$ ${M_N}_{DEF}$

第 $1$ 行包含两个整数 $N\ (1\leq N\leq 100,000)$ 和 $K\ (1\leq K\leq N)$ ，分别表示商店中怪兽的数量和要购买的怪兽数量。
接下来的 $N$ 行，每行包含两个整数，分别表示第 $i$ 只怪兽的攻击能力值和防御能力值 $({M_i}_{ATK},\ {M_i}_{DEF})\ (0\leq {M_i}_{ATK},\ {M_i}_{DEF}\leq 3000)$ 。

输出格式

第 $1$ 行输出能够达到的最小队伍不稳定度。

第 $2$ 行输出能够达到最小不稳定度的选法数对 $1000000007$ 取模的结果。

注意末尾需要换行。

输入输出样例

输入#1
```
4 3
0 0
1 1
3 3
2 2
```
输出#1
```
2
2
```
输入#2
```
4 2
1 1000
10 100
100 10
1000 1
```
输出#2
```
90
1
```
输入#3
```
3 1
1 1
2 2
3 3
```
输出#3
```
0
3
```

输入#4

输出#4

0
75135237

说明/提示

部分分

本题设置了部分分。

有 $10$ 分的测试点满足 $1\leq N\leq 20$ 。

样例解释 1

怪兽排列如下，选择 $3$ 只怪兽时，最小不稳定度为 $2$ 。同时，选法有 $2$ 种。

由 ChatGPT 4.1 翻译

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

首页