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)

while(true){
    (1) If you are at the destination, break.

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