Limits
1s, 512 MB

‘’True wisdom lies not in knowing all the answers, but in embracing the mystery of the unknown and allowing it to guide us towards new understandings.’’ - written by Artificial Intelligence.

Artificial intelligence (AI) has undoubtedly become increasingly powerful each day. Its ability to solve complex problems is one of the most remarkable advancements in recent times. Is it possible that one day humans will follow AI instructions without knowing what they are doing?

Imagine you are living in a world where AI is ruling. Every person follows AI instructions, and you are one of them.

In your imaginary world, there are $N$ portals, and each is numbered from $1$ to $N$. You can open any portal with some instructions given by artificial intelligence. In the beginning, all the portals are closed.

Each $i^{th} \: (1 \le i \le N)$ portal has a number written on it, denoted by $C_i$. if $C_i$ is positive every time you are on the $i^{th}$ portal, you will receive a reward of $C_i$ coins, whereas if $C_i$ is negative, you will be penalized and lose $C_i$ coins.

Initially, you have $0$ coins, and it is guaranteed that the instructions provided by the artificial intelligence will ensure that you always have a non-negative number of coins.

There are two types of instructions provided by artificial intelligence:

GOTO $i$: This instruction requires you to leave the current portal without closing it and open the $i^{th}$ portal. Initially, you are not at any portal.

PREVIOUS: This instruction instructs you to close the current portal and leave it. Then go to the portal opened exactly before it. If the AI instructs you to go previously, it is guaranteed that you previously came from another portal to the current portal.

You have been given $Q$ instructions to follow in order to collect coins. After following all the instructions, you need to determine the total number of coins you have obtained.

The first line of the input contains two positive integers $N$ and $Q$ $(1 \le N \le 10^5; \: 1 \le Q \le 10^6)$, separated by a space — the number of portals and instructions, respectively.

The second line contains $N$ integers $C_1, C_2, C_3,….., C_N \: (-10^3 \le C_i \le 10^3)$ — the number of coin in $i^{th}$ portal.

The instructions will be given in the following $Q$ lines.

Each line will either contain *"GOTO* $i$" $(1 \le i \le N)$ or *"PREVIOUS*" without quotation marks.

Output a single integer — indicating the total number of coins obtained after following all the instructions.

Input | Output |
---|---|

5 3 1 -3 4 0 9 GOTO 3 GOTO 2 PREVIOUS | 5 |

At first, you open the $3^{rd}$ portal and receive a reward of $4$ coins. Currently you have $0+4 = 4$ coins. Then, you leave the $3^{rd}$ portal without closing it. After that, you have to open the $2^{nd}$ portal and pay a penalty of $3$ coins. Currently you have $4-3 = 1$ coins. Lastly, you leave the $2^{nd}$ portal and closing it. Then, you have to go to the portal opened exactly before it, which is the $3^{rd}$ portal and receive $4$ coins as reward. Currently you have $1+ 4= 5$ coins. |

Login to submit.

70%
Solution Ratio

Billah_MasumEarliest,

pathanFastest, 0.1s

emon.088977Lightest, 4.9 MB

Shovon_AhmedShortest, 407B

Toph uses cookies. By continuing you agree to our Cookie Policy.