Is killing an innocent person strictly wrong ~ Victor, 2019
Victor has become obsessed with the Trolley Problem!
Victor found the original trolley problem too boring, so he has devised his own version.
In Victor's trolley problem, there is initially an array of trolleys,
days, and the
th trolley contains
people.
On the
th day, Victor lines up all the remaining trolleys, and picks a number
.
He will then partition his array into two subarrays,
and
(where
is the total number of trolleys on day
).
If
, then Victor will snap all the trolleys in
out of existence and set
equal to
. Otherwise, he will snap all the trolleys in
out of existence and set
equal to
.
Calculate the number of people Victor snaps on each day!
Constraints
for all
.
- The order of the trolleys will always remain the same.
for all
.
Input Specification
The first line will contain two space-separated integers and
, denoting the initial number of trolleys and the number of days respectively.
The next line will contain space-separated integers
, denoting the number of people in each trolley.
The next lines will each contain a single integer
.
Output Specification
For each day, output the number of people that Victor will snap out of existence on a new line.
Sample Input
8 3
6 1 3 2 9 10 2 4
4
1
1
Sample Output
25
6
5
Explanation of Sample Input
On the first day, and
. Then,
and
. Since
, Victor will snap trolleys
to
out of existence, leaving
as our array of trolleys.
On the second day, and
. Then,
and
. Since
, Victor will snap the first trolley and leave
as our array.
On the third and last day, and
. Then,
and
. Since
, Victor will snap the last two trolleys and leave
as our array.
Comments
I think the first test case has an extra space after the array input, so some Python solutions may not pass.
I removed the whitespace at the end of the line; however for future reference, you can circumvent this issue by simply using
.split()
rather than.split(' ')
.Should have just used C++!
I mentioned it due to a friend's submission, but you are definitely correct.
It's too bad that brute force O(ND) solutions passed during the contest, this was a nice prefix sum array problem.
You can prove that the brute force solution only takes
time, and was in fact intended.
Interesting, if there was no upper bound on a_k, would O(ND) be worst case.
Water is wet