RiseOJ – 최소 비용 경로

설명

농부 존의 목초지는 정사각형 "칸"들로 이루어진 $N\times M$ ( $2\le N\le 10^9$ , $2\le M\le 2\cdot 10^5$ ) 2차원 격자(거대한 체스판을 떠올려 보자)로 볼 수 있다. 위에서 $$x$$ 번째 행, 오른쪽에서 $$y$$ 번째 열에 있는 칸을 각 $x\in [1,N], y\in [1,M]$ 에 대해 $$(x,y)$$ 로 나타낸다. 또한 각 $y\in [1,M]$ 에 대해 $$y$$ 번째 열에는 비용 $$c_y$$ ( $1\le c_y\le 10^9$ )가 연관되어 있다.

베시는 칸 $$(1,1)$$ 에서 출발한다. 현재 칸 $$(x,y)$$ 에 있다면 다음 행동 중 하나를 할 수 있다.

$$y이면 베시는 비용 \(x^2$를 내고 다음 열로 이동할 수 있다($y$가 1 증가).$
$$x이면 베시는 비용 \(c_y$를 내고 다음 행으로 이동할 수 있다($x$가 1 증가).$

$$(x_i,y_i)$$ ( $x_i\in [1,N], y_i\in [1,M]$ ) 형태의 서로 독립적인 질의 $$Q$$ 개( $1\le Q\le 2\cdot 10^5$ )가 주어질 때, 각 질의에 대해 베시가 $$(1,1)$$ 에서 $$(x_i,y_i)$$ 로 이동하는 데 드는 총비용의 최솟값을 계산하시오.

문제 제공: Benjamin Qi

제약

배점

테스트 케이스 1-3은 $N,M\le 2000$ 을 만족한다.
테스트 케이스 4-8은 $c_2>c_3>\cdots>c_M$ 을 만족한다.
테스트 케이스 9-15는 $N\le 2\cdot 10^5$ 를 만족한다.
테스트 케이스 16-20에는 추가 제약이 없다.

문제 제공: Benjamin Qi

입력 형식

첫째 줄에 $$N$$ 과 $$M$$ 이 주어진다.

둘째 줄에 공백으로 구분된 $$M$$ 개의 정수 $c_1,c_2,\ldots,c_M$ 이 주어진다.

셋째 줄에 $$Q$$ 가 주어진다.

마지막 $$Q$$ 개의 줄 각각에는 공백으로 구분된 두 정수 $$x_i$$ 와 $$y_i$$ 가 주어진다.

출력 형식

각 질의에 대한 답을 $$Q$$ 개의 줄에 출력한다.

이 문제에 등장하는 정수가 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의한다.

예제 1

입력

5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4

출력

설명

The output in grid format:

    1  2  3  4
  *--*--*--*--*
1 | 0| 1| 2| 3|
  *--*--*--*--*
2 | 1| 5| 9|13|
  *--*--*--*--*
3 | 2|11|20|29|
  *--*--*--*--*
4 | 3|19|35|49|
  *--*--*--*--*
5 | 4|29|54|69|
  *--*--*--*--*

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > January > Platinum

올림피아드 > USACO > 2020-2021 > January > Platinum

태그

JudgeUSACO

최소 비용 경로

평가 및 의견

풀이 제출