QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 2048 MB 總分: 100

#8994. 节奏流

统计

你正在为一款名为 Rhythm Flow 的新热门音乐游戏设计评分算法,玩家必须跟随音乐节奏按下按钮。在 Rhythm Flow 的一轮游戏中,屏幕上会出现视觉指示器。玩家需要在这些时间点(且仅在这些时间点)按下按钮。然而,由于人类反应时间并非瞬间,游戏给予玩家一定的宽容度,接受在预期时间前后的几毫秒内按下的按钮。按得越准,得分越高。

下表列出了玩家根据实际按键时间与预期按键时间之间的差值(以毫秒为单位)所获得的积分:

时间差 (ms) 积分
$[0, 15]$ 7
$(15, 23]$ 6
$(23, 43]$ 4
$(43, 102]$ 2

误差在 103 毫秒或以上的极度不准确按键不得分。

在游戏过程中,玩家会按下若干次按钮。为了给游戏评分,需将每个实际按键与至多一个预期按键进行匹配,并遵循以下限制:如果一个实际按键发生在另一个实际按键之前,且两个按键都与预期按键匹配,则第一个按键对应的预期按键必须严格早于第二个按键对应的预期按键。

由于你非常慷慨,你决定计算出使玩家获得积分总数最大化的匹配方案。请计算在该匹配方案下,Rhythm Flow 这一轮游戏的最终得分。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2,000$),其中 $n$ 是预期按键次数,$m$ 是实际按键次数。

接下来的 $n$ 行,每行包含一个整数 $e$ ($1 \le e \le 10^9$)。这些是预期按键距离游戏开始的毫秒数。保证这些值是唯一的且按升序排列。

接下来的 $m$ 行,每行包含一个整数 $a$ ($1 \le a \le 10^9$)。这些是实际按键距离游戏开始的毫秒数。保证这些值是唯一的且按升序排列。

输出格式

输出一个整数:在最慷慨的评分引擎下,玩家所能获得的积分总数。

样例

样例输入 1

3 4
100
200
300
99
201
240
323

样例输出 1

20

样例输入 2

4 3
1000
2000
2500
3000
1103
2598
4000

样例输出 2

2

样例输入 3

2 2
100
144
56
100

样例输出 3

7

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.