Paired Up

题目描述

数轴上一共有 $N$（$1\le N\le 5000$）头奶牛，每头奶牛的品种为 Holstein 或 Guernsey。第 $i$ 头奶牛的品种为 $b_i\in \{H,G\}$，位置为 $x_i$（$0 \leq x_i \leq 10^9$），体重为 $y_i$（$1 \leq y_i \leq 10^5$）。 在 Farmer John 的信号下，一些奶牛会两两配对，要求： 每一对由一头 Holstein $h$ 和一头 Guernsey $g$ 组成，并且它们的位置相距不超过 $K$（$1\le K\le 10^9$）；即 $|x_h-x_g|\le K$。 每头奶牛要么属于恰好一对，要么不属于任何一对。 配对是极大的；也就是说，任意两头未配对的奶牛都不能再形成一对。 你需要确定未配对奶牛体重和的可能范围。具体地， 若 $T=1$，计算未配对奶牛体重和的最小可能值。 若 $T=2$，计算未配对奶牛体重和的最大可能值。

输入格式

第一行输入 $T$、$N$ 和 $K$。 接下来有 $N$ 行，第 $i$ 行包含 $b_i,x_i,y_i$。 保证 $0\le x_1< x_2< \cdots< x_N\le 10^9$。

输出格式

输出未配对奶牛体重和的最小值或最大值。

2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

16

1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

6

2 10 76
H 1 18
H 18 465
H 25 278
H 30 291
H 36 202
G 45 96
G 60 375
G 93 941
G 96 870
G 98 540

1893

提示

奶牛 $2$ 和 $3$ 可以配对，因为它们的距离为 $1$，不超过 $K = 4$。该配对是极大的，因为牛 $1$（唯一剩下的 Guernsey）到牛 $4$ 的距离为 $5$，到牛 $5$ 的距离为 $7$，都大于 $K = 4$。未配对奶牛的体重和为 $1 + 6 + 9 = 16$。 奶牛 $1$ 和 $2$ 可以配对，因为它们的距离为 $2 \leq K = 4$；奶牛 $3$ 和 $5$ 可以配对，因为它们的距离为 $4 \leq K = 4$。该配对是极大的，因为只剩下奶牛 $4$。未配对奶牛的体重和为唯一未配对奶牛的体重，即 $6$。 该样例的答案为 $18+465+870+540=1893$。 评分： 测试点 4-7 满足 $T=1$。 测试点 8-14 满足 $T=2$ 且 $N\le 300$。 测试点 15-22 满足 $T=2$。 注意：本题内存限制为 512MB，是默认值的两倍。 题目来源：Benjamin Qi

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum