AT_wtf22_day2_c.Jewel Pairs

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

有 $N$ 个宝石，编号为 $1$ 到 $N$ 。宝石 $i$ 的颜色为 $C_i$ ，价值为 $V_i$ 。其中颜色用 $1$ 到 $N$ 之间的整数表示。

两个宝石的配对 $(i,j)$ 当且仅当满足以下两个条件时被称为好的配对：

$C_i \neq C_j$
$V_i + V_j \leq L$

你需要从 $N$ 个宝石中选出若干个好的配对。每个宝石最多只能属于一个配对，但允许存在不属于任何配对的宝石。

请计算所选配对中所有宝石的价值总和的最大可能值。

输入格式

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

$N$ $L$
$C_1$ $V_1$
$C_2$ $V_2$
$\vdots$
$C_N$ $V_N$

输出格式

输出答案。

输入输出样例

输入#1
```
4 5
1 2
1 3
2 1
2 4
```
输出#1
```
4
```
输入#2
```
5 10
3 8
4 2
1 5
1 3
1 2
```
输出#2
```
17
```

输入#3

输出#3

输入#4

20 1000000000
15 239276621
15 910500852
15 245532750
15 715892722
16 80707349
15 257261830
12 950300098
15 322288793
15 256358887
15 504976376
2 907119713
15 152036484
13 298766520
15 480968804
15 285187325
13 755031424
15 69837029
15 88860861
9 596982638
15 272961035

输出#4

4704511147

说明/提示

约束条件

$1 \leq N \leq 250000$
$1 \leq L \leq 10^9$
$1 \leq C_i \leq N$
$0 \leq V_i \leq L$
所有输入值均为整数。

样例解释 1

配对 $(1,2)$ 不满足第一个条件，因此不是好的配对。配对 $(1,4)$ 不满足第二个条件。此样例的最优解是选择配对 $(2,3)$ 。

样例解释 2

此样例的最优解是选择配对 $(1,5)$ 和 $(2,3)$ 。

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

首页