No.3471 Load Balancing of Judge Servers
yuki2006Problem Statement
An online judge has $M$ judge servers (servers $1, 2, \ldots, M$). $N$ submissions are lined up in order in a queue, and they are assigned to servers one at a time, starting from the front.
Here, the load of a server is the total execution time of the submissions already assigned to that server.
Each submission is assigned to the server with the smallest current load at that moment. If multiple servers have the smallest load, it is assigned to the one with the smallest number.
The execution time of submission $i$ is $T_i$ milliseconds.
After all submissions have been assigned, find the time at which the last judging finishes (the maximum load among all servers).
Input
$N\ M$ $T_1\ T_2\ \ldots\ T_N$All constraint values are integers.
- $1 \le M \le N \le 200{,}000$
- $1 \le T_i \le 10^9$
Output
Print on one line the time at which all judging finishes. Print a newline at the end.
Sample
Sample 1
Input
5 2 2 3 7 5 1
Output
9
The assignment process:
Submission 1 (2ms) → Server 1 (loads: 2, 0)
Submission 2 (3ms) → Server 2 (loads: 2, 3)
Submission 3 (7ms) → Server 1 (loads: 9, 3)
Submission 4 (5ms) → Server 2 (loads: 9, 8)
Submission 5 (1ms) → Server 2 (loads: 9, 9)
The finish time is $\max(9, 9) = 9$.
Sample 2
Input
3 3 10 20 30
Output
30
Since there are 3 servers, one submission is assigned to each server. The longest execution time, 30ms, is the finish time.
Sample 3
Input
4 1 2 3 7 5
Output
17
Since there is only 1 server, all submissions are executed in order. It takes a total of $2 + 3 + 7 + 5 = 17$ ms.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。