25017번 - 플래피 버드 서브태스크언어 제한함수 구현

문제

여러분은 2014년에 한때 유행한 플래피 버드라는 게임을 아는가? 앞으로 전진하는 새가 화면 밖으로 넘어가거나 파이프에 충돌하지 않도록 상승과 낙하를 반복하면서 최대한 멀리 나아가는 게임이다.

플래피 버드 게임에 등장하는 새는 사실 교준이가 키우는 애완새 '안나'이다.

이차원 세계에 살고 있는 교준이와 새 안나는 오늘도 플래피 버드 게임과 비슷한 놀이를 하고 있다. 안나가 하늘을 날아다니면서 선분들을 지나면, 그 선분들의 가중치 합만큼 점수를 얻는 놀이이다.

이 놀이를 엄밀하게 서술하면 다음과 같다.

이차원 평면 위에 $x$축 또는 $y$축과 평행한 $N$개의 선분이 있다. $i$번 선분의 가중치는 $A_i$이고, 두 끝 점의 좌표는 $\left( X_{1, i}, Y_{1, i} \right),ドル $\left( X_{2, i}, Y_{2, i} \right)$다. $(0 \le i \le N-1)$

안나는 $x = 0$ 직선 위 원하는 점에서부터 $+x$ 방향으로 날기를 시작하고, $x = W$ 직선 위에 도달하면 날기를 종료한다. 그러나 안전상의 문제로, 안나는 $y = 0$보다 낮게 날거나 $y = H$보다 높게 날 수는 없다. 즉, 안나는 0ドル \le x \le W,ドル 0ドル \le y \le H$ 영역에서만 날 수 있다.

안나는 $x$축과 평행하게 날기 때문에 나는 도중에는 자신의 $y$ 좌푯값을 바꿀 수 없다. 그러나 단 한 번 교준이의 도움을 받아 나는 도중에 $y$축에 평행하게 상승 또는 낙하하여 $y$ 좌푯값을 바꿀 수 있다. 상승 및 낙하 과정에서 안나의 $x$ 좌푯값은 변하지 않으며, 상승과 낙하 둘 다 할 수는 없음에 유의하라.

안나의 이동 경로와 하나 이상의 점을 공유하는 모든 선분의 가중치 합이 안나가 얻는 점수이다.

예를 들어, $W = 5,ドル $H = 4$이고 $N = 7$개의 선분이 아래와 같이 놓여있다고 하자.

파란색 실선은 선분을, 점선은 안나의 이동 경로를 나타낸다. 원 안의 수는 선분 번호, 부호가 있는 수는 가중치를 의미한다.

만약 안나가 $(0, 1)$에서 날기 시작하고, $(2, 1)$에서 $(2, 4)$까지 상승한 다음, $(5, 4)$에서 날기를 마친다면, 0번, 1번, 2번, 4번, 6번 선분을 지나므로 $(-5)+(-1)+5+3+(-4) = -2$점의 점수를 얻는다.

그러나 안나가 $(0, 3.4)$에서 날기 시작하여, $(1.6, 3.4)$에서 $(1.6, 0.5)$까지 낙하한 후, $(5, 0.5)$에서 날기를 마친다면, 0번, 2번, 5번 선분을 지나므로 $(-5)+5+1 = 1$점의 점수를 얻는다.

$N$개의 선분에 대한 정보가 주어질 때, 안나가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하라.

함수 목록 및 정의

여러분은 아래 함수를 구현해야 한다.

long long get_max_score(int W, int H, vector<int> A, vector<int> X1, vector<int> Y1, vector<int> X2, vector<int> Y2)

• 이 함수는 단 한 번만 호출된다.
• 인자로 주어지는 정수 배열 A, X1, Y1, X2, Y2의 크기는 $N$이다. 배열의 각 원소 A[$i$], X1[$i$], Y1[$i$], X2[$i$], Y2[$i$]는 각각 $A_i,ドル $X_{1, i},ドル $Y_{1, i},ドル $X_{2, i},ドル $Y_{2, i}$를 나타낸다. $(0 \le i \le N-1)$
• 이 함수는 안나가 얻을 수 있는 최대 점수를 반환하여야 한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

입력

출력

제한

• 입력에서 주어지는 모든 수는 정수이다.
• 2ドル \le W \le 100,000円$
• 1ドル \le H \le 100,000円$
• 1ドル \le N \le 250,000円$
• 1ドル \le X_{i, j} \le W-1$ $(i \in \{ 1, 2 \}, 0 \le j \le N-1)$
• 0ドル \le Y_{i, j} \le H$ $(i \in \{ 1, 2 \}, 0 \le j \le N-1)$
• $-1,000円,000円,000円 \le A_i \le 1,000円,000円,000円$ $(0 \le i \le N-1)$
• 모든 0ドル \le i \le N-1$에 대하여, $X_{1, i} = X_{2, i}$ 또는 $Y_{1, i} = Y_{2, i}$.
• 모든 선분의 길이는 양수이다. 즉, 모든 0ドル \le i \le N-1$에 대하여, $\left( X_{1, i}, Y_{1, i} \right) \ne \left( X_{2, i}, Y_{2, i} \right)$.

서브태스크 1 (7점)

• $W \le 50$
• $H \le 50$
• $N \le 50$

서브태스크 2 (8점)

• $W \le 50$
• $H \le 50$

서브태스크 3 (10점)

• $N \le 500$

서브태스크 4 (14점)

• $N \le 8,000円$

서브태스크 5 (15점)

• $X_{1, i} = X_{2, i}$ $(0 \le i \le N-1)$

서브태스크 6 (10점)

• $Y_{1, i} = Y_{2, i}$ $(0 \le i \le N-1)$

서브태스크 7 (36점)

• 추가적인 제약 조건이 없다.

힌트

예제 1

$W = 2,ドル $H = 1,ドル $N = 2,ドル $A =$ [6, -10], $X_1 =$ [1, 1], $Y_1 =$ [0, 0], $X_2 =$ [1, 1], $Y_2 =$ [1, 1] 인 경우를 생각해 보자.

그레이더는 다음 함수를 호출한다.

get_max_score(2, 1, [6, -10], [1, 1], [0, 0], [1, 1], [1, 1]) = -4

아래 그림은 $N$개의 선분과 최대 점수를 얻을 수 있는 안나의 경로를 나타낸다.

안나가 $(0, 1)$에서 날기 시작하여, 상승이나 낙하를 하지 않고 $(2, 1)$에서 종료하면, 0번, 1번 선분의 점수를 획득하여 총 6ドル + (-10) = -4$점을 얻는다.

이 예제는 부분문제 1, 2, 3, 4, 5, 7의 조건을 만족한다.

예제 2

$W = 5,ドル $H = 4,ドル $N = 5,ドル $A =$ [1, 1, 1, 1, -1], $X_1 =$ [1, 2, 3, 1, 2], $Y_1 =$ [0, 1, 1, 3, 1], $X_2 =$ [1, 2, 3, 4, 4], $Y_2 =$ [2, 2, 4, 3, 1] 인 경우를 생각해 보자.

그레이더는 다음 함수를 호출한다.

get_max_score(5, 4, [1, 1, 1, 1, -1], [1, 2, 3, 1, 2],
 [0, 1, 1, 3, 1], [1, 2, 3, 4, 4], [2, 2, 4, 3, 1]) = 4

이 예제는 부분문제 1, 2, 3, 4, 7의 조건을 만족한다.

예제 3

$W = 11,ドル $H = 8,ドル $N = 11,ドル $A =$ [1, -3, 0, -2, 2, 7, -1, -1, -1, -2, -1], $X_1 =$ [5, 2, 10, 3, 2, 7, 4, 8, 7, 7, 10], $Y_1 =$ [5, 4, 1, 3, 0, 8, 2, 3, 8, 5, 5] $X_2 =$ [5, 10, 8, 3, 2, 10, 1, 8, 10, 7, 8], $Y_2 =$ [1, 4, 1, 7, 4, 8, 2, 8, 8, 6, 5] 인 경우를 생각해 보자.

그레이더는 다음 함수를 호출한다.

get_max_score(11, 8,
 [1, -3, 0, -2, 2, 7, -1, -1, -1, -2, -1],
 [5, 2, 10, 3, 2, 7, 4, 8, 7, 7, 10],
 [5, 4, 1, 3, 0, 8, 2, 3, 8, 5, 5],
 [5, 10, 8, 3, 2, 10, 1, 8, 10, 7, 8],
 [1, 4, 1, 7, 4, 8, 2, 8, 8, 6, 5]) = 5

이 예제는 부분문제 1, 2, 3, 4, 7의 조건을 만족한다.

샘플 그레이더

Sample grader는 아래와 같은 형식으로 입력을 받는다.

• Line 1: $W$ $H$ $N$
• Line 2 + $i$ $(0 \le i \le N-1)$: $A_i$ $X_{1, i}$ $Y_{1, i}$ $X_{2, i}$ $Y_{2, i}$

Sample grader는 다음을 출력한다.

• Line 1: 함수 get_max_score가 반환한 값

Sample grader는 실제 채점에서 사용하는 그레이더와 다름에 유의하라.

첨부

• flappybird_public.zip