CT57187

Parth's jobs Cooldown Queue

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the lantern district of Glowfen, Parth records each jobs in a worn leather ledger. The guild wants answers, not guesses. Task: n tasks of types 0..T must run with at least k idle/other tasks between two same-type tasks. Print the minimum total time including any needed idles. Input format: First line: n and k. Second line: n task types. Output format: Print the minimum completion time. Constraints: 1 <= n <= 4000; 0 <= k <= 100; 0 <= type < 26.

Example 1:

Input: 3300 11 15 5 23 19 9 7 22 15 8 5 16 1 4 17 13 19 6 12 10 14 16 9 15 8 13 7 25 22 22 24 1 0 0 7 9 23 13 14 20 16 13 16 0 5 20 13 5 24 22 15 21 17 6 13 19 19 23 2 14 6 10 19 12 16 21 19 1 21 25 9 15 2 5 13 22 22 3 10 2 21 14 16 16 9 14 25 4 4 24 25 21 25 23 24 14 1 11 10 12 15 14 4 18 10 21 17 10 6 22 25 22 4 24 7 4 16 16 16 25 6 2 11 16 19 16 16 3 19 23 0 12 25 11 12 24 1 24 21 17 15 7 15 8 0 19 10 5 23 21 0 24 14 23 3 14 14 5 9 24 23 5 17 1 24 9 18 22 6 20 13 2 23 5 12 8 17 5 19 0 21 23 2 18 6 1 24 5 22 20 3 11 25 22 15 7 23 24 4 6 21 16 9 5 17 6 5 10 2 24 24 25 5 15 17 4 9 17 9 9 9 8 23 5 2 16 24 14 6 21 25 14 25 20 0 6 8 23 17 7 17 2 6 1 9 25 2 13 18 8 24 8 24 16 5 0 14 8 9 21 24 9 9 5 4 6 23 16 20 13 22 6 0 25 4 11 5 11 15 9 9 0 20 5 21 20 10 20 13 0 4 13 3 5 9 13 1 20 1 25 24 9 18 7 20…
Output: 3300

Example 2:

Input: 1409 9 0 15 9 9 6 15 20 22 19 13 21 4 9 16 25 8 12 15 25 18 1 8 9 19 23 12 18 20 14 10 10 24 9 17 2 16 20 25 7 16 5 13 2 25 17 12 10 7 25 24 25 23 5 23 1 20 20 0 25 3 9 24 15 19 8 19 21 8 11 25 16 24 1 3 15 20 21 18 17 23 10 5 14 10 21 5 16 15 10 12 16 12 2 18 2 6 23 10 23 17 3 2 15 13 10 5 16 25 21 10 14 5 18 17 25 14 6 10 10 13 6 2 23 11 17 12 18 12 5 2 8 25 15 17 10 12 3 10 2 18 3 10 16 18 24 9 19 3 11 5 12 25 25 16 13 3 16 2 0 13 15 12 22 6 24 12 24 14 20 21 3 14 9 14 3 24 10 15 1 16 25 4 2 21 2 24 10 16 1 11 23 9 19 15 2 1 5 6 14 4 25 4 18 25 25 4 0 15 7 6 1 24 15 17 1 16 0 10 5 6 0 6 12 6 0 19 5 18 11 12 18 6 25 12 13 18 11 4 16 23 12 22 25 4 9 12 12 9 11 18 0 14 6 23 6 22 0 17 5 22 2 0 5 3 7 15 20 2 19 23 9 23 20 4 21 6 14 9 6 11 13 19 15 17 12 9 4 13 8 16 19 1 9 17 15 1 19 24 4 16 …
Output: 1409

Example 3:

Input: 1923 10 3 22 23 12 25 7 1 10 1 3 18 20 19 0 14 4 11 9 23 9 18 19 19 9 17 14 8 4 6 13 10 17 5 1 21 19 9 5 1 6 14 17 6 3 13 24 3 19 19 21 18 20 1 16 0 18 11 7 2 19 15 21 6 11 1 7 21 19 4 15 9 17 0 4 6 18 9 11 5 25 14 14 5 19 0 11 16 20 5 7 0 21 6 21 19 2 19 23 8 9 2 15 13 22 9 7 5 19 12 3 5 23 15 4 14 19 23 11 7 3 19 6 2 17 3 10 8 0 11 8 22 11 5 23 4 5 24 0 8 3 8 25 13 9 7 23 25 21 22 17 3 15 6 18 8 1 0 21 0 11 10 16 8 25 12 21 9 13 2 23 5 13 2 5 14 19 22 15 16 18 21 4 25 24 5 1 19 23 6 22 3 6 23 12 5 23 6 18 5 5 24 20 16 21 4 14 18 25 7 15 11 11 11 11 5 6 0 20 25 5 21 13 25 12 13 15 25 17 22 9 24 24 18 1 23 5 10 0 20 19 1 2 3 20 10 13 15 18 0 10 8 17 22 11 11 9 23 15 16 12 25 24 16 17 2 16 20 24 16 12 13 22 12 14 0 21 2 20 13 21 24 0 11 0 7 3 13 22 11 16 9 23 2 12 8 22 9 13 21 13 3 25 2 16 …
Output: 1923

Constraints:

1 <= n <= 4000; 0 <= k <= 100; 0 <= type < 26.

Loading...
Test Cases:No test cases
No test cases available.