# KOITST 22 Flappy Bird

https://www.acmicpc.net/problem/25017

Do you remember the game Flappy Bird, which was popular for a while in 2014? It's a game where a bird moves forward and the player controls it to avoid hitting pipes or flying out of the screen, by repeatedly ascending and descending to go as far as possible.

The bird that appears in the Flappy Bird game is actually a pet bird named 'Anna' raised by Kyojun.

Kyojun and the bird Anna, who live in a two-dimensional world, are playing a game similar to Flappy Bird today. In this game, when Anna flies through segments in the sky, she earns points equal to the sum of the weights of those segments.

A formal description of this game is as follows:

In a two-dimensional plane, there are $N$ $(0 \leq i \leq N-1)$ segments parallel to the $x$ or $y$-axis. The weight of the $i$-th segment is $A_i$, and the coordinates of the two endpoints are $(X_{1, i}, Y_{1, i})$ and $(X_{2, i}, Y_{2, i})$.

Anna starts flying from any point on the $x = 0$ line and ends her flight when she reaches the $x = W$ line. However, for safety reasons, Anna cannot fly below $y = 0$ or above $y = H$. In other words, Anna can only fly in the range $0 \leq x \leq W$ and $0 \leq y \leq H$.

Since Anna flies parallel to the $x$-axis, she cannot change her $y$-coordinate during flight. However, with Kyojun's help, she can ascend or descend parallel to the $y$-axis once during flight. Note that Anna's $x$-coordinate does not change during ascent or descent, and she cannot both ascend and descend.

The score Anna earns is the sum of the weights of all segments that share one or more points with her path.

For example, if $W = 5$, $H = 4$, and there are $7$ segments positioned as follows:


If Anna starts flying at $(0, 1)$, ascends from $(2, 1)$ to $(2, 4)$, and ends her flight at $(5, 4)$, she passes segments $0$, $1$, $2$, $4$, and $6$, earning a score of $(-5) + (-1) + 5 + 3 + (-4) = -2$. (Orange line)

However, if Anna starts flying at $(0, 3.4)$, descends from $(1.6, 3.4)$ to $(1.6, 0.5)$, and ends her flight at $(5, 0.5)$, she passes segments $0$, $2$, and $5$, earning a score of $(-5) + 5 + 1 = 1$. (Green line)

Given information about $N$ segments, write a program to determine the maximum score Anna can earn.

## Function List and Definitions

You need to implement the following function:

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

* This function is called only once.
* The size of the integer arrays A, X1, Y1, X2, Y2 given as arguments is $N$. Each element of the arrays A[$i$], X1[$i$], Y1[$i$], X2[$i$], Y2[$i$] represents $A_i$, $X_{1, i}$, $Y_{1, i}$, $X_{2, i}$, $Y_{2, i}$, respectively.
* $(0 \leq i \leq N-1)$
* This function should return the maximum score that Anna can obtain.
* No input/output functions should be executed in any part of the submitted source code.

## Constraints

All numbers given in the input are integers.

* $2 \leq W \leq 100,000$
* $1 \leq H \leq 100,000$
* $1 \leq N \leq 250,000$
* $1 \leq X_{i, j} \leq W-1$ $(i \in {1, 2}, 0 \leq j \leq N-1)$
* $0 \leq Y_{i, j} \leq H$ $(i \in {1, 2}, 0 \leq j \leq N-1)$
* $-1,000,000,000 \leq A_i \leq 1,000,000,000$ $(0 \leq i \leq N-1)$
* For all $0 \leq i \leq N-1$, either $X_{1, i} = X_{2, i}$ or $Y_{1, i} = Y_{2, i}$.
* All segments have positive lengths. That is, for all $0 \leq i \leq N-1$,
* $(X_{1, i}, Y_{1, i}) \neq (X_{2, i}, Y_{2, i})$.

## Subtasks

1. $W \leq 50$, $H \leq 50$, $N \leq 50$ (7 points)
1. $W \leq 50$, $H \leq 50$ (8 points)
1. $N \leq 500$ (10 points)
1. $N \leq 8,000$ (14 points)
1. $X_{1, i} = X_{2, i}$ $(0 \leq i \leq N-1)$ (15 points)
1. $Y_{1, i} = Y_{2, i}$ $(0 \leq i \leq N-1)$ (10 points)
1. No additional constraints (36 points)

## Example 1

Let's consider the case where $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].

The grader calls the following function:

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

The figure below shows Anna's path and the maximum score she can achieve with $N$ segments.

If Anna starts flying at $(0, 1)$, doesn't ascend or descend, and ends her flight at $(2, 1)$, she passes segments 0 and 1, earning a score of $6 + (-10) = -4$.

This example satisfies the conditions of subproblems 1, 2, 3, 4, 5, and 7.

Example 2

Let's consider the case where $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].

The grader calls the following function:

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

This example satisfies the conditions of subproblems 1, 2, 3, 4, and 7.

Sure, here's the translation:

Function List and Definitions

You need to implement the following function:

latex

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

This function is called only once.
The size of the integer arrays A, X1, Y1, X2, Y2 given as arguments is $N$. Each element of the arrays A[$i$], X1[$i$], Y1[$i$], X2[$i$], Y2[$i$] represents $A_i$, $X_{1, i}$, $Y_{1, i}$, $X_{2, i}$, $Y_{2, i}$, respectively.
$(0 \leq i \leq N-1)$
This function should return the maximum score that Anna can obtain.

No input/output functions should be executed in any part of the submitted source code.

Constraints

All numbers given in the input are integers.

$2 \leq W \leq 100,000$

$1 \leq H \leq 100,000$

$1 \leq N \leq 250,000$

$1 \leq X_{i, j} \leq W-1$ $(i \in {1, 2}, 0 \leq j \leq N-1)$

$0 \leq Y_{i, j} \leq H$ $(i \in {1, 2}, 0 \leq j \leq N-1)$

$-1,000,000,000 \leq A_i \leq 1,000,000,000$ $(0 \leq i \leq N-1)$

For all $0 \leq i \leq N-1$, either $X_{1, i} = X_{2, i}$ or $Y_{1, i} = Y_{2, i}$.

All segments have positive lengths. That is, for all $0 \leq i \leq N-1$,

$(X_{1, i}, Y_{1, i}) \neq (X_{2, i}, Y_{2, i})$.

Subtasks

$W \leq 50$, $H \leq 50$, $N \leq 50$ (7 points)
$W \leq 50$, $H \leq 50$ (8 points)
$N \leq 500$ (10 points)
$N \leq 8,000$ (14 points)
$X_{1, i} = X_{2, i}$ $(0 \leq i \leq N-1)$ (15 points)
$Y_{1, i} = Y_{2, i}$ $(0 \leq i \leq N-1)$ (10 points)
No additional constraints (36 points)

Example 1

Let's consider the case where $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].

The grader calls the following function:

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

The figure below shows Anna's path and the maximum score she can achieve with $N$ segments.

If Anna starts flying at $(0, 1)$, doesn't ascend or descend, and ends her flight at $(2, 1)$, she passes segments 0 and 1, earning a score of $6 + (-10) = -4$.

This example satisfies the conditions of subproblems 1, 2, 3, 4, 5, and 7.

Example 2

Let's consider the case where $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].

The grader calls the following function:

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

This example satisfies the conditions of subproblems 1, 2, 3, 4, and 7.

Example 3

Let's consider the case where $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].

The grader calls the following function:

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

This example satisfies the conditions of subproblems 1, 2, 3, 4, and 7.