레이팅 미적용농부 존은 고속도로를 따라 길게 뻗은 농장을 소유하고 있으며, 이는 1차원 수직선처럼 볼 수 있다. 농장을 따라 \(K\)개의 풀밭 (\(1 \leq K \leq 2\cdot 10^5\))이 있고, \(i\)번째 풀밭은 위치 \(p_i\)에 있으며 맛있는 정도 \(t_i\) (\(0\le t_i\le 10^9\))를 가진다. 농부 존의 라이벌인 농부 노즈는 이미 자신의 소 \(M\)마리 (\(1 \leq M \leq 2\cdot 10^5\))를 위치 \(f_1 \ldots f_M\)에 배치해 두었다. 이 \(K+M\)개의 위치는 모두 \([0,10^9]\) 범위의 서로 다른 정수이다.
농부 존은 자기 소들을 배치할 \(N\) (\(1\le N\le 2\cdot 10^5\))개의 위치(정수가 아니어도 된다)를 골라야 한다. 이 위치들은 농부 노즈의 소들이 이미 차지한 위치와 달라야 하지만, 농부 존의 소를 풀밭과 같은 위치에 두는 것은 가능하다.
어떤 풀밭에 가장 가까운 소를 가진 농부가 그 풀밭의 소유권을 주장할 수 있다. 라이벌 농부의 두 소가 풀밭에서 같은 거리에 있으면 농부 노즈가 그 풀밭을 차지한다.
농부 노즈의 소들의 위치와 풀밭들의 위치 및 맛있는 정도가 주어질 때, 농부 존의 소들을 최적으로 배치했을 때 차지할 수 있는 맛있는 정도의 총합의 최댓값을 구하시오.
출제자: Brian Dean
출제자: Brian Dean
첫째 줄에 \(K\), \(M\), \(N\)이 주어진다.
다음 \(K\)개의 줄에 각각 공백으로 구분된 두 정수 \(p_i\)와 \(t_i\)가 주어진다.
다음 \(M\)개의 줄에 각각 정수 \(f_i\)가 하나씩 주어진다.
맛있는 정도의 총합의 최댓값을 나타내는 정수를 출력한다. 이 문제의 답은 32비트 정수에 담기에 너무 클 수 있으므로 64비트 정수(예: C나 C++의 "long long")를 사용하는 것이 좋다.
6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
1136If Farmer John places cows at positions \(11.5\) and \(8\) then he can claim a total tastiness
of
\(10+12+14=36\).
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Silver