레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 2배인 4초이다.*
농부 존의 \(N\)마리 소들(\(1\le N\le 1.5\cdot 10^5\))은 정수 우유 생산량 \(a_1,\dots,a_N\)을 가진다. 즉, \(i\)번째 소는 분당 \(a_i\) 단위의 우유를 생산하며, \(0 \leq a_i \leq 10^8\)이다.
매일 아침, 농부 존은 \(N\)마리 소 모두를 헛간의 착유기에 연결한 상태로 시작한다. 그는 소들을 한 마리씩 분리하여 매일의 운동을 위해 내보내야 한다. 첫 번째로 내보내는 소는 착유 1분 만에 분리되고, 두 번째로 내보내는 소는 그로부터 1분 더 착유한 후 분리되는 식이다. 첫 번째 소(소 \(x\)라 하자)는 착유기에서 1분만 보내므로, 총 우유에 \(a_x\) 단위만 기여한다. 두 번째 소(소 \(y\)라 하자)는 착유기에서 총 2분을 보내므로, 총 우유에 \(2a_y\) 단위를 기여한다. 세 번째 소(소 \(z\)라 하자)는 총 \(3a_z\) 단위를 기여하는 식이다. 농부 존이 최적의 순서로 소들을 분리할 때 수집할 수 있는 총 우유의 최대 가능량을 \(T\)라 하자.
농부 존은 자기 소 떼의 일부 우유 생산량이 달랐다면 \(T\)가 어떻게 변할지 궁금하다. \(Q\)개의 쿼리(\(1\le Q\le 1.5\cdot 10^5\)) 각각은 두 정수 \(i\)와 \(j\)로 주어지며, \(a_i\)를 \(j\)로 바꾸었을 때 \(T\)의 새로운 값을 계산하라 (\(0 \leq j \leq 10^8\)). 각 쿼리는 다른 모든 쿼리와 독립적인 일시적 변경을 고려한다는 점에 유의하라. 즉, 다음 쿼리를 고려하기 전에 \(a_i\)는 원래 값으로 되돌아간다.
출제자: Benjamin Qi
배점
- 입력 2-4: \(N,Q\le 1000\)
- 입력 5-11: 추가 제약 조건이 없다.
출제자: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(a_1\dots a_N\)이 주어진다.
셋째 줄에 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에는 각각 공백으로 구분된 두 정수 \(i\)와 \(j\)가 주어진다.
\(Q\)개의 쿼리 각각에 대한 \(T\)의 값을 각 줄에 출력한다.
5
1 10 4 2 6
3
2 1
2 8
4 555
81
98For the first query, \(a\) would become \([1,1,4,2,6]\), and
$T =
1 \cdot 1 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 4 + 5 \cdot 6 = 55$.
For the second query, \(a\) would become \([1,8,4,2,6]\), and
$T =
1 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + 4 \cdot 6 + 5 \cdot 8 = 81$.
For the third query, \(a\) would become \([1,10,4,5,6]\), and
$T =
1 \cdot 1 + 2 \cdot 4 + 3 \cdot 5 + 4 \cdot 6 + 5 \cdot 10 = 98$.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > US Open > Silver