#PU1165. USACO 2021 December Contest, Platinum — Problem 2. Paired Up

    ID: 1199 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec21来源:usaco.orgscoring:equal_test_cases双指针

USACO 2021 December Contest, Platinum — Problem 2. Paired Up

USACO 2021 December Contest, Platinum — Problem 2. Paired Up

题目描述

There are a total of NN (1≤N≤50001\le N\le 5000) cows on the number line, each of which is a Holstein or a Guernsey. The breed of the ii-th cow is given by bi∈{H,G}b_i\in \{H,G\}, the location of the ii-th cow is given by xix_i (0≤xi≤1090 \leq x_i \leq 10^9), and the weight of the ii-th cow is given by yiy_i (1≤yi≤1051 \leq y_i \leq 10^5). At Farmer John's signal, some of the cows will form pairs such that Every pair consists of a Holstein hh and a Guernsey gg whose locations are within KK of each other (1≤K≤1091\le K\le 10^9); that is, ∣xh−xg∣≤K|x_h-x_g|\le K. Every cow is either part of a single pair or not part of a pair. The pairing is maximal; that is, no two unpaired cows can form a pair. It's up to you to determine the range of possible sums of weights of the unpaired cows. Specifically, If T=1T=1, compute the minimum possible sum of weights of the unpaired cows. If T=2T=2, compute the maximum possible sum of weights of the unpaired cows.

输入格式

The first input line contains TT, NN, and KK. Following this are NN lines, the ii-th of which contains bi,xi,yib_i,x_i,y_i. It is guaranteed that 0≤x1<x2<⋯<xN≤1090\le x_1< x_2< \cdots< x_N\le 10^9.

输出格式

The minimum or maximum possible sum of weights of the unpaired cows.

数据范围

Test cases 4-7 satisfy T=1T=1. Test cases 8-14 satisfy T=2T=2 and N≤300N\le 300. Test cases 15-22 satisfy T=2T=2. Note: the memory limit for this problem is 512MB, twice the default. Problem credits: Benjamin Qi

样例

样例 1

2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
16
Cows $2$ and $3$ can pair up because they are at distance $1$, which is at most
$K = 4$. This pairing is maximal, because cow $1$, the only remaining Guernsey,
is at distance $5$ from cow $4$ and distance $7$ from cow $5$, which are more
than $K = 4$. The sum of weights of unpaired cows is
$1 + 6 + 9 = 16$.

样例 2

1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
6
Cows $1$ and $2$ can pair up because they are at distance $2 \leq K = 4$, and
cows $3$ and $5$ can pair up because they are at distance $4 \leq K = 4$. This
pairing is maximal because only cow $4$ remains. The sum of weights of
unpaired cows is the weight of the only unpaired cow, which is simply $6$.

样例 3

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
The answer to this example is $18+465+870+540=1893$.