AdditionalFile4273.zip

#4273. 「KTSC 2022 R1」飞扬的小鸟

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "flappybird.h"。

题目描述

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T2 「플래피 버드」

你知道 2014 年曾经流行的游戏「Flappy Bird」吗？这是一款游戏，玩家需要控制一只小鸟在前进的过程中避免撞到管道或飞出屏幕，通过不断上升和下降尽可能地飞得更远。

在这个游戏中出现的小鸟其实是教准养的宠物鸟“安娜”。教准和安娜今天也在二维世界中玩类似于「Flappy Bird」的游戏。安娜在天空中飞行，经过线段时会根据线段的权重获得相应的分数。

这个游戏的规则如下： 在二维平面上有 $N$ 条与 $x$ 轴或 $y$ 轴平行的线段。第 $i$ $(0 \leq i \leq N-1)$ 条线段的权重为 $A_{i}$，两个端点的坐标分别为 $\left(X_{1, i}, Y_{1, i}\right)$ 和 $\left(X_{2, i}, Y_{2, i}\right)$。

安娜从 $x=0$ 直线上的任意点开始向 $+x$ 方向飞行，当到达 $x=W$ 直线时结束飞行。但出于安全考虑，安娜不能飞到 $y=0$ 以下或 $y=H$ 以上。也就是说，安娜只能在 $0 \leq x \leq W, 0 \leq y \leq 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] $(0 \leq i \leq N-1)$ 分别表示 $A_{i}, X_{1, i}, Y_{1, i}, X_{2, i}, Y_{2, i}$。
• 该函数返回安娜可以获得的最大分数。

注意，提交的代码中不应包含任何输入输出操作。

样例 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$ 的条件。

数据范围与提示

对于所有输入数据，满足：

• 输入中给定的所有数都是整数。
• $2 \leq W \leq 10^5$
• $1 \leq H \leq 10^5$
• $1 \leq N \leq 2.5\cdot 10^5$
• $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)$
• $-10^9 \leq A_{i} \leq 10^9$ $(0 \leq i \leq N-1)$
• 对于每个 $0 \leq i \leq N-1$，$X_{1, i}=X_{2, i}$ 或 $Y_{1, i}=Y_{2, i}$。
• 所有线段的长度都是正数。即，对于每个 $0 \leq i \leq N-1$，$\left(X_{1, i}, Y_{1, i}\right) \neq \left(X_{2, i}, Y_{2, i}\right)$。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$7$	$W \leq 50$；$H \leq 50$；$N \leq 50$
$2$	$8$	$W \leq 50$；$H \leq 50$
$3$	$10$	$N \leq 500$
$4$	$14$	$N \leq 8000$
$5$	$15$	$X_{1, i}=X_{2, i}$ $(0 \leq i \leq N-1)$
$6$	$10$	$Y_{1, i}=Y_{2, i}$ $(0 \leq i \leq N-1)$
$7$	$36$	无附加限制

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$W\,H\,N$
• 第 $2+i$ $(0 \leq i \leq N-1)$ 行：$A_{i}\,X_{1, i}\,Y_{1, i}\,X_{2, i}\,Y_{2, i}$

示例评测程序按以下格式输出：

• 第 $1$ 行：函数 get_max_score 返回的值

示例评测程序可能与实际评测程序不同。