레이팅 미적용수직선 위에 총 \(N\)마리(\(1\le N\le 10^5\))의 소가 있다. \(i\)번째 소의 위치는 \(x_i\)(\(0 \leq x_i \leq 10^9\))이고, \(i\)번째 소의 무게는 \(y_i\)(\(1 \leq y_i \leq 10^4\))이다.
농부 존의 신호에 맞춰, 일부 소들이 다음 조건을 만족하도록 쌍을 이룬다.
- 모든 쌍은 위치가 서로 \(K\) 이내(\(1\le K\le 10^9\))인 서로 다른 두 소 \(a\)와 \(b\)로 이루어진다. 즉, \(|x_a-x_b|\le K\)이다.
- 모든 소는 정확히 하나의 쌍에 속하거나 어떤 쌍에도 속하지 않는다.
- 이 짝짓기는 극대(maximal)이다. 즉, 쌍을 이루지 않은 어떤 두 소도 쌍을 이룰 수 없다.
쌍을 이루지 않은 소들의 무게 합이 가질 수 있는 범위를 구하는 것이 당신의 일이다. 구체적으로,
- \(T=1\)이면, 쌍을 이루지 않은 소들의 무게 합의 최솟값을 구한다.
- \(T=2\)이면, 쌍을 이루지 않은 소들의 무게 합의 최댓값을 구한다.
출제자: Benjamin Qi
배점
- 테스트 케이스 4-8은 \(T=1\)을 만족한다.
- 테스트 케이스 9-14는 \(T=2\)와 \(N\le 5000\)을 만족한다.
- 테스트 케이스 15-20은 \(T=2\)를 만족한다.
출제자: Benjamin Qi
입력의 첫째 줄에 \(T\), \(N\), \(K\)가 주어진다.
다음 \(N\)개의 줄 중 \(i\)번째 줄에 \(x_i\)와 \(y_i\)가 주어진다. \(0\le x_1< x_2< \cdots< x_N\le 10^9\)이 보장된다.
쌍을 이루지 않은 소들의 무게 합의 최솟값 또는 최댓값을 출력한다.
2 5 2
1 2
3 2
4 2
5 1
7 26In this example, cows \(2\) and \(4\) can pair up because they are at distance \(2\),
which is at most \(K = 2\). This pairing is maximal, because cows \(1\) and \(3\) are
at distance \(3\), cows \(3\) and \(5\) are at distance \(3\), and cows \(1\) and \(5\) are
at distance \(6\), all of which are more than \(K = 2\). The sum of weights of
unpaired cows is
\(2 + 2 + 2 = 6\).
1 5 2
1 2
3 2
4 2
5 1
7 22Here, cows \(1\) and \(2\) can pair up because they are at distance \(2 \leq K = 2\),
and cows \(4\) and \(5\) can pair up because they are at distance \(2 \leq K = 2\).
This pairing is maximal because only cow \(3\) remains. The weight of the
only unpaired cow here is simply \(2\).
2 15 7
3 693
10 196
12 182
14 22
15 587
31 773
38 458
39 58
40 583
41 992
84 565
86 897
92 197
96 146
99 7852470The answer for this example is \(693+992+785=2470\).
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Gold