Paired Up
플래티넘 II의견: 0
There are a total of \(N\) (\(1\le N\le 5000\)) cows on the number line, each of
which is a Holstein or a Guernsey. The breed of the \(i\)-th cow is given by
\(b_i\in \{H,G\}\), the location of the \(i\)-th cow is given by \(x_i\)
(\(0 \leq x_i \leq 10^9\)), and the weight of the \(i\)-th cow is given by
\(y_i\) (\(1 \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 \(h\) and a Guernsey \(g\) whose locations are within \(K\) of each other (\(1\le K\le 10^9\)); that is, \(|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=1\), compute the minimum possible sum of weights of the unpaired cows.
- If \(T=2\), compute the maximum possible sum of weights of the unpaired cows.
Problem credits: Benjamin Qi
SCORING
- Test cases 4-7 satisfy \(T=1\).
- Test cases 8-14 satisfy \(T=2\) and \(N\le 300\).
- Test cases 15-22 satisfy \(T=2\).
Problem credits: Benjamin Qi
The first input line contains \(T\), \(N\), and \(K\).
Following this are \(N\) lines, the \(i\)-th of which contains \(b_i,x_i,y_i\). It is
guaranteed that \(0\le x_1< x_2< \cdots< x_N\le 10^9\).
The minimum or maximum possible sum of weights of the unpaired cows.
2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 916Cows \(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\).
1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 96Cows \(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\).
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 5401893The answer to this example is \(18+465+870+540=1893\).
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Platinum
평가 및 의견
Paired Up
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Paired Up