Rhythm Flow
InterviewTime limit1sMemory limit1024 MB
Match expected and actual presses in order, each at most once, to maximize the total points, where each pair scores 7, 6, 4, 2, or 0 based on the time gap.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Array
- Solved
- No attempts yet
Problem
You are designing a scoring algorithm for the new hit rhythm game Rhythm Flow, where players must press a button in time with the music. During a round, there are points in time when a visual indicator flashes on the screen. Players are expected to press the button at those times, and only at those times. Human reaction time is not instantaneous, so the game accepts a press a few milliseconds earlier or later than expected. More accurate presses are worth more points.
The following table lists how many points a player gets depending on how far the actual press is from the expected press, in milliseconds:
Presses with a difference of milliseconds or more score no points.
During gameplay, the player presses the button some number of times. Each actual press is matched with at most one expected press, with this restriction: if one actual press happens before another actual press and both are matched, then the expected press matched to the first must be strictly before the expected press matched to the second.
You want the matching that maximizes the total points. Compute the final score of the round under this matching.
Input
The first line contains two integers and (), where is the number of expected button presses and is the number of actual button presses.
Each of the next lines contains a single integer (), the times of the expected button presses in milliseconds from the start of the round. These values are unique and sorted in increasing order.
Each of the next lines contains a single integer (), the times of the actual button presses in milliseconds from the start of the round. These values are unique and sorted in increasing order.
Output
Output a single integer: the total number of points the player earns under a maximally generous scoring engine.