34067번 - Lawnmower 서브태스크다국어언어 제한함수 구현

문제

After his adventures in Poenari Fortress, Vlad returns home and, as a true Romanian, his first thought is that he should feed his horse. The horse is not very picky when it comes to food, so Vlad uses his lawn as a primary source of food for it.

For this task, Vlad has a lawn mower of capacity $c$. He decided to split his lawn into $n$ lanes, numbered from 0ドル$ to $n − 1,ドル which he has to mow in this order. Each lane $i$ contains a quantity of uncut grass $v[i]$ and, due to some unknown reasons, it takes $a[i]$ seconds for Vlad to push the mower over that lane.

After going over a few lanes, the mower may reach full capacity, in which case it stops cutting grass, leaving some on that lane. Every time that happens, its collector tank needs to be emptied, which takes $b$ seconds and can be done only at the end of a lane. If the collector tank fills up while Vlad is going over lane $i,ドル he needs to keep pushing the mower until the end of the lane, empty the tank and then go over the lane one more time (or as many times as needed) in order to cut the left-over grass. For example if for a lane $i$ we have to pass through it 3ドル$ times to get rid of all the grass, that will take $a[i] + b + a[i] + b + a[i]$ seconds. After mowing the entire lawn, the mower must be emptied.

After a lot of thinking and complaining that it will take him way too much to finish mowing, Vlad arrived at the conclusion that sometimes it might be more time-efficient to empty the collector tank even before it reaches full capacity, but he is not sure what is the best strategy he can use. Therefore, he asks for your help.

Given the quantity of grass on each lane and the number of seconds it takes to push the mower over each lane, the capacity of the tank and the time it takes to empty it, find the best way for Vlad to finish mowing his lawn in minimum time.

구현 상세

You should implement the following procedure.

long long mow(int n, int c, int b, std::vector<int> &a, std::vector<int> &v);

• $n$: the number of lanes of the lawn
• $c$: the total capacity of the collector tank
• $b$: the number of seconds to empty the tank
• $a$: vector of length $n$ describing the time it takes to go over each lane
• $v$: vector of length $n$ giving the quantity of grass on each lane
• This procedure should return a single integer, the minimum time to mow the lawn.
• This procedure is called exactly once for each test case.

입력

출력

제한

• 1ドル ≤ n ≤ 200,円 000$
• 1ドル ≤ a[i] ≤ 10^9$ (for each $i$ such that 0ドル ≤ i < n$)
• 1ドル ≤ v[i] ≤ 10^9$ (for each $i$ such that 0ドル ≤ i < n$)
• 1ドル ≤ b ≤ 10^9$
• 1ドル ≤ c ≤ 10^9$
• It is guaranteed that the correct result will be at most 10ドル^{18}$

서브태스크

힌트

예제

Example 1

Consider the following call:

mow(3, 5, 2, {2, 10, 3}, {2, 4, 6})

In this sample, there are 3ドル$ lanes, the collector tank has a capacity of 5ドル$ and it takes 2ドル$ seconds to empty it.

For this sample, Vlad will mow the first lane in 2ドル$ seconds. The amount of grass in the mower will be 2ドル$. Then he will empty the mower in 2ドル$ seconds. On the first strip, he spends 4ドル$ seconds.

He will then pass through the second lane. He will mow 4ドル$ units of grass. He will choose not to empty the tank after finishing the second strip. The time spent on the second strip is 10ドル$ seconds.

For the third strip, he starts mowing. After one unit of grass, his mower fills up, thus he has to go until the end of the strip, empty the mower, then start mowing through third strip again. Keep in mind that after the entire yard is mowed, the mower has to be emptied. The time spent on the third strip is 3ドル + 2 + 3 + 2 = 10$ seconds.

In total, he spends 4ドル + 10 + 10 = 24$ seconds. It can be proven that this is the optimal strategy that Vlad uses to mow the lawn.

Example 2

Consider the following call:

mow(4, 10, 4, {1, 2, 1, 4}, {3, 2, 6, 7})

In this sample, there are 4ドル$ lanes, the collector tank has a capacity of 10ドル$ and it takes 4ドル$ seconds to empty it.

The optimal strategy is just to go over the first 3ドル$ lanes and afterwards the tank will be filled and the vector of grass quantities will be [0, 0, 1, 7]. After that, the tank should be emptied and the last 2ドル$ lanes will be mowed and the tank will be emptied again at the end.

The total number of seconds will be $a[0] + a[1] + a[2] + b + a[2] + a[3] + b = 17$.

샘플 그레이더

The sample grader reads the input in the following format:

• line 1ドル$: $n$ $c$ $b$
• line 2ドル$: $a[0]$ $a[1]$ $\dots$ $a[n − 1]$
• line 3ドル$: $v[0]$ $v[1]$ $\dots$ $v[n − 1]$

and outputs the result of the call to mow with the corresponding parameters.

첨부

• lawn.h sample-grader.cpp