DMPG '16 G4 - Araxxi - Olympiads Online Judge

DMPG '16 G4 - Araxxi

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

FatalEagle

Problem type

You are playing a game called RuinScape and are currently fighting a tough boss named Araxxi (she is a spider). The fight will last for $N$ $N$ units of time. Araxxi has $M$ $M$ types of special attacks that she uses, numbered from $1$ $1$ to $M$ $M$ , and she will use a single special attack during each of the $N$ $N$ units of time. She always uses the same sequence of special attacks, and some special attacks may be repeated in this sequence more than once.

Since you are a skilled player, you know that the key to winning the fight is to counter as many of Araxxi's special attacks as you can. You know the techniques to counter each of the $M$ $M$ special attacks. Once you activate a technique, all of Araxxi's special attacks that the technique counters will be countered, but you will be hit by all of Araxxi's other special attacks that she uses.

Activating a technique is done on the same unit of time as, but an infinitesimal amount of time before Araxxi's special attack (so if Araxxi uses the attack your technique counters on that unit of time, you will successfully counter it). You can switch techniques during the fight, but after cancelling a technique, there is a delay before you can activate the next technique, meaning you must take unavoidable damage from the special attacks that occur during the delay after you cancel the current technique. Specifically, if the delay has a value $d$ $d$ , that means you cannot activate another technique until you take damage $d$ $d$ times. This delay may be different for different techniques. If you play optimally, what is the maximum number of special attacks can you counter?

Input Specification

The first line of input will contain two integers $N$ $N$ and $M$ $M$ .
The second line of input will contain $N$ $N$ integers, the sequence of special attacks Araxxi uses, in order. Each integer will be between $1$ $1$ and $M$ $M$ , inclusive.
The third line of input will contain $M$ $M$ integers, the $i^\text{th}$ $i^{th}$ of which is the delay for the technique to counter Araxxi's $i^\text{th}$ $i^{th}$ attack. Each integer will be between $0$ $0$ and $N-1$ $N - 1$ , inclusive.

Output Specification

The first and only line of output should contain the maximum number of special attacks you can counter.

Constraints

For all subtasks:

$1 \le M \le N \le 100\,000$ $1 \leq M \leq N \leq 100 000$

Subtask 1 [20%]

$N \le 1000$ $N \leq 1000$

Subtask 2 [20%]

$M = 2$ $M = 2$

Subtask 3 [20%]

All the delays are equal to $1$ $1$ .

Subtask 4 [40%]

No additional constraints.

Sample Input

Copy

5 2
1 2 2 1 2
0 2

Sample Output

Copy

Explanation of Output for Sample Input

The optimal strategy is to activate the technique to counter type 1 special attacks just before Araxxi uses her first attack, and immediately after, switch to the technique to counter type 2 special attacks and keep using that technique until the end of the fight. You will get hit by one type 1 attack, but you will have managed to counter 4 attacks.

Comments

4

aCookieBreak commented on June 13, 2016, 3:32 p.m. ← edit 2 →

Kappa.

2

FatalEagle commented on June 13, 2016, 9:04 p.m.

kc?

4

aCookieBreak commented on June 14, 2016, 5:54 p.m. ← edit 2 →

2

FatalEagle commented on June 15, 2016, 1:12 a.m.

Add me

1

aCookieBreak commented on June 15, 2016, 7:48 p.m.

Added.