#USACOC2211B. Paired Up

Paired Up

题目描述

数轴上总计有 NN 头奶牛,每一头奶牛都是荷斯坦牛(Holstein)或更赛牛(Guernsey)之一。第 ii 头奶牛的品种为 bi{H,G}b_i\in \{{\tt H},{\tt G}\},第 ii 头奶牛的位置为 xix_i,而第 ii 头奶牛的重量为 yiy_i

根据 Farmer John 的信号,某些奶牛会组成对,使得

  • 每一对包含位置相差不超过 KK 的一头荷斯坦牛 hh 和一头更赛牛 gg;也就是说,xhxgK|x_h-x_g|\le K
  • 每一头奶牛要么包含在恰好一对中,要么不属于任何一对。
  • 配对是极大的;也就是说,没有两头未配对的奶牛可以组成对。

你需要求出未配对的奶牛的重量之和的可能的范围。具体地说,

  • 如果 T=1T=1,计算未配对的奶牛的最小重量和。
  • 如果 T=2T=2,计算未配对的奶牛的最大重量和。
  • 1N50001\le N\le 5000
  • 1K1091\le K\le 10^9
  • 0xi1090 \leq x_i \leq 10^9
  • 1yi1051 \leq y_i \leq 10^5

输入格式

输入的第一行包含 TTNNKK

以下 NN 行,第 ii 行包含 bi,xi,yib_i,x_i,y_i。输入保证 0x1<x2<<xN1090\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
2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

奶牛 2233 可以配对,因为她们的距离为 11,不超过 K=4K = 4。这个配对方案是极大的,因为奶牛 11,唯一余下的更赛牛,和奶牛 44 的距离为 55,和奶牛 55 的距离为 77,均大于 K=4K = 4。未配对的奶牛的重量和为 1+6+9=161 + 6 + 9 = 16

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

奶牛 1122 可以配对,因为她们的距离为 2K=42 \leq K = 4,同时奶牛 3355 可以配对,因为她们的距离为 4K=44 \leq K = 4。这个配对方案是极大的,因为只剩下了奶牛 44。未配对的奶牛的重量和即为唯一未配对的奶牛的重量,即为 66

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
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

测试点性质

  • 测试点 4-7 满足 T=1T=1
  • 测试点 8-14 满足 T=2T=2N300N\le 300
  • 测试点 15-22 满足 T=2T=2

注意:本题的内存限制为 512MB,通常限制的两倍。

题目提供者

Benjamin Qi