Food Expo (APCS 2021-09 Expert)

Points 100 2.0s 512M

There are \(n\) food stalls at a food expo. Each stall sells exactly one type of food. Their food types, in order, are \(a_1,a_2,\ldots,a_n\); different stalls may sell the same type of food.

The king and his ministers form a group of \(k\) tasters. Each taster may choose one contiguous segment of stalls, and no food type may occur more than once in a taster's segment. Segments chosen by different tasters must not overlap. A taster who is not assigned a segment may skip tasting.

Given \(n\), \(k\), and the food type at each stall, find the maximum total number of stalls that the tasters can visit.

Input

The first line contains two positive integers \(n\) and \(k\), the number of stalls and the number of tasters.

The second line contains \(n\) positive integers \(a_1,a_2,\ldots,a_n\), the food types sold at the stalls in order.

Constraints

  • \(1 \le n \le 10^6\)
  • \(1 \le k \le 20\)
  • \(1 \le n\times k \le 5\times 10^6\)
  • \(1 \le a_i \le 10^5\)

Output

Output one integer: the maximum total number of stalls that the \(k\) tasters can visit.

Scoring

There are \(20\) scored test cases. Each test case is worth \(5\) points.

Subtask Points Additional constraints
1 50 \(k=1\)
2 50 No additional constraints

Sample Input 1

5 1
1 2 1 3 1

Sample Output 1

3

Sample Input 2

10 3
1 7 1 3 1 4 4 2 7 4

Sample Output 2

8

Source

APCS September 2021, Programming Problem 4; ZeroJudge g278 Food Expo.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.