레이팅 미적용농부 존이 농장 전체에 건초 더미를 배분하고 있다!
농부 존의 농장에는 \(N\) \((1\le N\le 2\cdot 10^5)\)개의 헛간이 있으며, 수직선 위의 정수 좌표 \(x_1,\dots, x_N\) \((0 \le x_i \le 10^6)\)에 위치한다. 농부 존의 계획은 먼저 \(N\)개의 건초 더미 수송분을 어떤 정수 지점 \(y\) \((0 \le y \le 10^6)\)로 배송받은 다음, 각 헛간에 수송분을 하나씩 배분하는 것이다.
안타깝게도 농부 존의 배분 서비스는 매우 낭비가 심하다. 구체적으로, 어떤 \(a_i\)와 \(b_i\) \((1\le a_i, b_i\le 10^6)\)에 대해, 각 수송분을 왼쪽으로 한 단위 거리 운반할 때마다 건초 더미 \(a_i\)개가 낭비되고, 오른쪽으로 한 단위 거리 운반할 때마다 건초 더미 \(b_i\)개가 낭비된다. 형식적으로, 지점 \(y\)에서 지점 \(x\)에 있는 헛간으로 수송분을 운반할 때 낭비되는 건초 더미의 수는 다음과 같다.
$$ \begin{cases} a_i\cdot (y-x) & \text{if } y \ge x \\ b_i\cdot (x-y) & \text{if } x > y \end{cases}. $$
각각 가능한 \((a_i,b_i)\) 값으로 이루어진 \(Q\) \((1\le Q\le 2\cdot 10^5)\)개의 독립적인 쿼리가 주어질 때, 농부 존이 \(y\)를 최적으로 선택하면 낭비되는 건초 더미의 최소 개수가 얼마인지 구하라.
문제 제공: Benjamin Qi
채점 방식
- 입력 2: \(N,Q\le 10\)
- 입력 3: \(N,Q\le 500\)
- 입력 4-6: \(N,Q\le 5000\)
- 입력 7-16: 추가 제약 조건 없음.
문제 제공: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 줄에 \(x_1\dots x_N\)이 주어진다.
다음 줄에 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각각 두 정수 \(a_i\)와 \(b_i\)가 주어진다.
\(Q\)개의 줄을 출력한다. \(i\)번째 줄에 \(i\)번째 쿼리의 답을 출력한다.
5
1 4 2 3 10
4
1 1
2 1
1 2
1 411
13
18
30For example, to answer the second query, it is optimal to select \(y=2\). Then the
number of wasted haybales is equal to
\(2(2-1)+2(2-2)+1(3-2)+1(4-2)+1(10-2)=1+0+1+2+8=13\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Gold