레이팅 미적용수직선 위에 총 \(N\)마리(\(1\le N\le 5000\))의 소가 있으며, 각 소는 홀스타인 또는 건지 품종이다. \(i\)번째 소의 품종은 \(b_i\in \{H,G\}\)로 주어지고, \(i\)번째 소의 위치는 \(x_i\)(\(0 \leq x_i \leq 10^9\)), \(i\)번째 소의 무게는 \(y_i\)(\(1 \leq y_i \leq 10^5\))로 주어진다.
농부 존의 신호에 맞춰, 일부 소들이 다음 조건을 만족하도록 쌍을 이룬다.
- 모든 쌍은 위치가 서로 \(K\) 이내(\(1\le K\le 10^9\))인 홀스타인 \(h\)와 건지 \(g\)로 이루어진다. 즉, \(|x_h-x_g|\le K\)이다.
- 모든 소는 정확히 하나의 쌍에 속하거나 어떤 쌍에도 속하지 않는다.
- 이 짝짓기는 극대(maximal)이다. 즉, 쌍을 이루지 않은 어떤 두 소도 쌍을 이룰 수 없다.
쌍을 이루지 않은 소들의 무게 합이 가질 수 있는 범위를 구하는 것이 당신의 일이다. 구체적으로,
- \(T=1\)이면, 쌍을 이루지 않은 소들의 무게 합의 최솟값을 구한다.
- \(T=2\)이면, 쌍을 이루지 않은 소들의 무게 합의 최댓값을 구한다.
출제자: Benjamin Qi
배점
- 테스트 케이스 4-7은 \(T=1\)을 만족한다.
- 테스트 케이스 8-14는 \(T=2\)와 \(N\le 300\)을 만족한다.
- 테스트 케이스 15-22는 \(T=2\)를 만족한다.
출제자: Benjamin Qi
입력의 첫째 줄에 \(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 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