TLE '16 Contest 5 P2 - Playing Piano - DMOJ: Modern Online Judge

TLE '16 Contest 5 P2 - Playing Piano

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

ZQFMGB12

Problem type

The CS Nerd wants to play as well as this performer, but he realizes that he'll likely never be able to do so.

The CS Nerd knows that playing music can impress girls, so he decides to learn how to play some passionate piano solos in order to impress the girl. He thinks that pieces with fast moving notes are fun to play and will make the girl think he is a piano virtuoso. In particular, he has a liking for the super chord.

A piano's notes are numbered starting from $1$ $1$ , from the left side. A super chord is formed as follows:

Choose the first note of the chord. This can be any note.
Repeat the following steps from the starting note: Jump right $4$ $4$ notes, then $3$ $3$ notes, then $3$ $3$ notes, then $2$ $2$ notes.
These steps can be repeated in the reverse order from the starting note by jumping left (i.e. left down $2$ $2$ , then $3$ $3$ , then $3$ $3$ , then $4$ $4$ ).

A consecutive sequence of notes is considered to be a super sequence if every single note in the sequence is part of the same super chord. For example, the sequences $1,5,8,11,13$ $1, 5, 8, 11, 13$ and $11,5,1,1,17,32$ $11, 5, 1, 1, 17, 32$ are super sequences formed using the super chord starting from note $1$ $1$ .

The CS Nerd finds a manuscript with $N$ $N$ notes on it; the $i^\text{th}$ $i^{th}$ note on the manuscript corresponds to note $p_i$ $p_{i}$ on the piano. He wants to know the length of the longest super sequence. Since the manuscript is old, the CS Nerd is allowed to change up to $K$ $K$ notes. Can you help the CS Nerd?

Constraints

$1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$

$0 \le K \le N$ $0 \leq K \leq N$

$1 \le p_i \le 10^9$ $1 \leq p_{i} \leq 10^{9}$

For 20% of the points, $N \le 50$ $N \leq 50$ and $K \le 2$ $K \leq 2$ .

For an additional 30% of the points, $N \le 1\,000$ $N \leq 1 000$ .

Input Specification

The first line of input will contain two space-separated integers: $N$ $N$ and $K$ $K$ .

$N$ $N$ lines of input follow. The $i^\text{th}$ $i^{th}$ line will contain $p_i$ $p_{i}$ .

Output Specification

On a single line, output the length of the longest super sequence after the CS Nerd changes up to $K$ $K$ notes.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

The CS Nerd can change the $4^\text{th}$ $4^{th}$ note from $5$ $5$ to $4$ $4$ . By doing this, the continuous subsequence of $4$ $4$ notes starting from the $2^\text{nd}$ $2^{nd}$ note are all part of a super chord starting from note $4$ $4$ .

Comments

0

jlsajfj commented on Jan. 20, 2017, 12:23 a.m. ← edit 2 →

Does the super chord have to start from the lowest note, or can it start from any note. IE: super chord 1 = 1 5 8 11 13. Is 5 8 11 a super chord?

0

leonchen0613 commented on Jan. 19, 2017, 5:42 p.m.

How is 11, 5, 1, 1, 17, 32 a super sequence?

3

d commented on Jan. 19, 2017, 5:46 p.m.

All of the notes are in the same super chord.