DAPC23-042.Idle Terminal

Medium · 1 s · 256 MB

icpc
dapc
2023

It is migration day at the Big Administration Processing Company: the database containing all administrative documents of all clients needs to be migrated to the latest version of the database software. Quite some things have changed over the past years, and this software has not been upgraded, so the number of migration jobs is high.

The migration jobs run in parallel on the multicore server machine in a first-come-first-serve fashion: every time a core is done running a job, it starts running the first job that has not yet started. The Idle Terminal (IT) Team is sitting huddled around the terminal window, eagerly awaiting the dopamine boost when another migration job completes successfully and a message is printed to the terminal.

The IT Team starts breaking out in sweat when nothing changes on the terminal for quite a long time. Did the connection hang? Has the server soft-locked? Did all jobs get stuck in infinite loops?? On the other hand, some migration jobs really do have a long duration, and it may simply be a coincidence that there are only long-running jobs active at the time. To calm down the IT Team, you decide to compute the longest time that goes by without seeing a new message on the terminal, starting from the moment that the first migration jobs start running.

Giriş formatı

The input consists of:

• One line with two integers $n$ and $k$ ( $1 \leq n, k \leq 10^5$ ), the number of migration jobs and the number of cores in the server machine.

• One line with $n$ integers $d$ ( $1 \leq d \leq 100$ ), the duration of each job in the order that they are processed.

Çıxış formatı

Output the longest time that goes by without seeing a new message on the terminal.

Qeyd

Source: Delft Algorithm Programming Contest 2023 · Author: Ragnar Groot Koerkamp · License: CC BY-SA 4.0 · Original: https://dapc.wisv.ch · Statement adapted for AlgoLens and shared under the same license.

Nümunələr

Giriş #1

2 2
3 7

Çıxış #1

Giriş #2

5 10
1 2 3 4 5

Çıxış #2

Giriş #3

4 1
2 10 6 4

Çıxış #3

Giriş #4

6 2
3 5 8 10 4 1

Çıxış #4

Giriş #5

6 3
2 4 6 6 6 6

Çıxış #5

Giriş formatı

The input consists of:

• One line with two integers $n$ and $k$ ( $1 \leq n, k \leq 10^5$ ), the number of migration jobs and the number of cores in the server machine.

• One line with $n$ integers $d$ ( $1 \leq d \leq 100$ ), the duration of each job in the order that they are processed.