Problem: Link

Submission: Link $$$O(n)$$$, 92ms!

Part1: Hint

By looking at the $$$4$$$ test cases, we find that answers for $$$b[i] = 1$$$ are the same.

Part2: The greedy strategy (for each index $$$i$$$)

First, we define some macros for convenience:

The previous index of $$$x$$$: #define pr(x) ((x) == 1 ? n : (x) - 1)

The next index of $$$x$$$: #define ne(x) ((x) == n ? 1 : (x) + 1)

If $$$b[x]==1$$$, rt(x) denotes the place of the next $$$1$$$ in the loop: rt(x). For example, let $$$b$$$ be an $$$1$$$-indexed array $$$[2, 1, 2, 1]$$$, then $$$rt(2)==4$$$ and $$$rt(4)==2$$$. Note that $$$rt(i)==i$$$ could happen, for example, $$$b==[2, 1, 2]$$$, then $$$rt(2)==2$$$. rt could be pre-calculated using a stack.

get(i, j): The gas need to go from $$$i$$$ to $$$j$$$, both inclusive and $$$1$$$-indexed. For example, if $$$a=[1, 2, 3, 4]$$$, then $$$get(1, 2)==a[1]+a[2]==1+2==3$$$ and $$$get(4, 2)==a[4]+a[1]+a[2]==4+1+2==7$$$. The $$$get$$$ function could be pre-calculated using the prefix sum.

We need to maintain an array $$$c$$$ in the algorithm. $$$c[i]$$$ denotes the minimum burbles we need to pay from the previous place $$$j$$$ where $$$b[j]==1$$$ to $$$i$$$. $$$j$$$ may be equal to $$$1$$$. For example, if $$$b==[1, 2, 1]$$$, then $$$c[3]$$$ denotes the minimum burbles we need to pay from $$$3$$$ to $$$3$$$, which is $$$a[3]$$$. $$$c[2]$$$ denotes the minimum burbles we need to pay from $$$1$$$ to $$$2$$$. Note that this $$$c$$$ is well-defined iff there's at least one $$$i$$$ such that $$$b[i]==1$$$. So we just need to output the case where all $$$b[i]$$$ equal to $$$2$$$.

//The Initialpoint
int i = initialpoint;
while(true){
    (1) If you are at the destination, which is the same as the initialpoint, goto finish.

    (2) When you stay at i where b[i]==2, just pay 2a[i] for a[i] gas that enables you to move from i to ne(i). let i = ne(i);

    (3) When you stay at i where b[i]==1, set initialized2 = true and curi = i, and do the following inner while loop. Also, we need to calculate the array c.
    while(initialized2 || curi != rt(i)){ 
        //rt(i): The next i in this trip with b[i]==1
        //Why do we need this initialized2? Because curi before the loop is i, which may be equal to rt(i) at the beginning, in this case we still need to go into this loop!
        if(curi == initialpoint) goto finish;
        initialized2 = false;
        if(get(i, curi) <= k) c[curi] = get(i, curi);
        else c[curi] = k + 2*(get(i, curi) - k); //By k gas at i using k burbles and the left get(i, curi) - k gas using 2*(get(i, curi) - k) burbles.
        curi = ne(curi);
    }
}
finish:

The correctness of the algorithm could be proved by verifying that, whenever this algorithm is forced to buy one gas using two burbles, every other strategy needs to.