Rhythm Flow

면접 대비

시간 제한1초메모리 제한1024 MB

요약
실제 버튼 입력을 순서를 지켜 기대 입력에 많아야 하나씩 짝지어, 시간 차에 따른 점수 표로 얻는 총점의 최댓값을 구한다.
난이도

보통10점 중 5점

유형
동적 계획법, 투 포인터, 정렬
정답자
아직 제출이 없습니다

문제

You are designing a scoring algorithm for the new hit rhythm game Rhythm Flow where players must press a button in time to the music. During a round of Rhythm Flow, 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). However, since human reaction time is not instantaneous, the game gives the player some leeway and accepts a button 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 away the actual button press is from the expected button press, in milliseconds:

Time Difference (ms)Points
\[0,15]\[0,15]7
(15,23](15,23]6
(23,43](23,43]4
(43,102](43,102]2

Wildly inaccurate presses with a difference of 103103 milliseconds or more score no points.

During gameplay, the player presses the button some number of times. To score the game, match each actual button press with at most one expected button press, with the following restriction: if one actual button press happens before another actual button press and both button presses are matched with expected button presses, then the expected button press for the first must be strictly before the expected button press for the second.

Because you are generous, you decide to compute the matching that maximizes the number of points the player earns. Compute the final score of the round of Rhythm Flow under this matching.

입력

The first line contains two integers nn and mm (1≤n,m≤2,0001≤n,m≤2\\,000), where nn is the number of expected button presses and mm is the number of actual button presses.

Each of the next nn lines contains a single integer ee (1≤e≤1091≤e≤10^9). These are the times of the expected button presses in milliseconds from the start of the round. It is guaranteed that these values are unique and in sorted order.

Each of the next mm lines contains a single integer aa (1≤a≤1091≤a≤10^9). These are the times of the actual button presses in milliseconds from the start of the round. It is guaranteed that these values are unique and in sorted order.

출력

Output a single integer: the total number of points the player earns given a maximally-generous scoring engine.

예제3

  1. 예제 1

    입력
    3 4
    100
    200
    300
    99
    201
    240
    323
    
    예상 출력
    20
    
  2. 예제 2

    입력
    4 3
    1000
    2000
    2500
    3000
    1103
    2598
    4000
    
    예상 출력
    2
    
  3. 예제 3

    입력
    2 2
    100
    144
    56
    100
    
    예상 출력
    7