Elevators of Tamem
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2700
Tags: dp

There is a building named Taman Membeku (shortened as Tamem). The building has $$$N$$$ floors numbered from $$$1$$$ to $$$N$$$ from bottom to top. The only way to move between floors in the building is to use elevators. There are $$$3$$$ elevators available in Tamem, namely elevators $$$1$$$, $$$2$$$, and $$$3$$$.

Pak Chanek works as an elevator operator in Tamem. Pak Chanek will work for $$$Q$$$ days. Initially, each elevator is in floor $$$1$$$ and all elevators are on. On each day, exactly one of the following will happen:

- 1 x y – There is a person currently in floor $$$x$$$ who wants to go to floor $$$y$$$. ($$$1\leq x,y\leq N$$$; $$$x\neq y$$$)
- 2 p – Elevator $$$p$$$ changes state at the start of the day. If previously it is on, then it will turn off. If previously it is off, then it will turn on. ($$$1\leq p\leq3$$$)

For each day, Pak Chanek can control the movement of all elevators as he pleases. However, for each day where there is a person currently in floor $$$x$$$ who wants to go to floor $$$y$$$, among all elevator movements done by Pak Chanek, the following must happen:

1. One elevator moves to floor $$$x$$$.
2. The person gets into the elevator.
3. The elevator moves to floor $$$y$$$.
4. The person gets out of the elevator.

For each day, Pak Chanek can only move the elevators that are currently on. Note that, since a change in state happens at the start of the day, this means that an elevator that turns off on some day starts becoming unusable from that day itself. Conversely, an elevator that turns on on some day starts becoming usable from that day itself.

It is known that the electricity fee for each day is different. More specifically, on the $$$j$$$-th day, the fee needed to move one elevator up or down by one floor is $$$A_j$$$.

From the start, Pak Chanek already knows the electricity fees and the sequence of events that will happen on the $$$Q$$$ days, so Pak Chanek can operate the elevators strategically. What is the minimum possible electricity fee to fulfill all needs of the people who want to move between floors in Tamem? Note: in the end, each elevator does not have to go back to floor $$$1$$$.

Input format:
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$2\leq N\leq10^5$$$; $$$1\leq Q\leq300$$$) — the number of floors and the number of days.

The second line contains $$$Q$$$ integers $$$A_1, A_2, A_3 \ldots, A_Q$$$ ($$$1 \leq A_j \leq 10^5$$$) — the electricity fee for each day.

The $$$j$$$-th of the next $$$Q$$$ lines contains the $$$j$$$-th event as described. At any moment, there will always be at least one elevator that is on.

Output format:
An integer representing the minimum possible electricity fee to fulfill all needs of the people who want to move between floors in Tamem.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
The following is an example of an optimal strategy:

1. On the $$$1$$$-st day:   Elevator $$$2$$$ moves to floor $$$3$$$.  Elevator $$$3$$$ moves to floor $$$2$$$, picks the person up, moves to floor $$$7$$$, then drops the person off.
2. On the $$$2$$$-nd day:   Elevator $$$2$$$ picks the person up, moves to floor $$$9$$$, then drops the person off.
3. On the $$$3$$$-rd day:   Elevator $$$2$$$ turns off.
4. On the $$$4$$$-th day:   Elevator $$$3$$$ moves to floor $$$4$$$, picks the person up, moves to floor $$$5$$$, drops the person off, then moves to floor $$$3$$$.
5. On the $$$5$$$-th day:   Elevator $$$3$$$ picks the person up, moves to floor $$$5$$$, then drops the person off.
6. On the $$$6$$$-th day:   Elevator $$$2$$$ turns on.  Elevator $$$1$$$ moves to floor $$$2$$$.  Elevator $$$2$$$ moves to floor $$$7$$$.
7. On the $$$7$$$-th day:   Elevator $$$2$$$ picks the person up, moves to floor $$$3$$$, then drops the person off.
8. On the $$$8$$$-th day:   Elevator $$$1$$$ picks the person up, moves to floor $$$1$$$, then drops the person off.

The total electricity fee for each day from the $$$1$$$-st day to the $$$8$$$-th day are $$$24$$$, $$$24$$$, $$$0$$$, $$$18$$$, $$$8$$$, $$$6$$$, $$$28$$$, and $$$6$$$ respectively. Therefore, the total electricity fee for the entire $$$Q$$$ days is $$$24+24+0+18+8+6+28+6=114$$$.

It can be obtained that there is no strategy that requires a smaller electricity fee.

Example input:
9 8
3 4 4 3 4 2 7 6
1 2 7
1 3 9
2 2
1 4 5
1 3 5
2 2
1 7 3
1 2 1

Example output:
114

Editorial:
First, let's solve the problem if there are no events of type $$$2$$$. We can solve this problem using dynamic programming. First, define:
• $$$\text{enter}[e]$$$: the initial floor of the person in the $$$e$$$-th event.
• $$$\text{exit}[e]$$$: the desired floor of the person in the $$$e$$$-th event.
Then, define $$$\text{dp}[i][j][k]$$$ as the minimum electricity fee if:
• Elevator $$$1$$$ last moved at the $$$i$$$-th event (last at floor $$$\text{exit}[i]$$$).
• Elevator $$$2$$$ last moved at the $$$j$$$-th event (last at floor $$$\text{exit}[j]$$$).
• Elevator $$$3$$$ last moved at the $$$k$$$-th event (last at floor $$$\text{exit}[k]$$$).
Let's say we have handled all events from the $$$1$$$-st to the ($$$e-1$$$)-th and now we want to handle the $$$e$$$-th event. This means the electricity fee for the the current condition is a value of $$$\text{dp}[i][j][k]$$$ with $$$\max(i,j,k)=e-1$$$ and we want to choose one elevator to handle the $$$e$$$-th event. If we choose elevator $$$1$$$, then it can move between the $$$i$$$-th day and $$$e$$$-th day to prepare for the person in the $$$e$$$-th event. So the minimum electricity fee for elevator $$$1$$$ to handle this is $$$|\text{exit}[i]-\text{enter}[e]|\times\min(A_i,A_{i+1},\ldots,A_e)+|\text{enter}[e]-\text{exit}[e]|\times A_e$$$. So we add that value with $$$\text{dp}[i][j][k]$$$ for a candidate value of $$$\text{dp}[e][j][k]$$$. We do a similar thing for elevators $$$2$$$ and $$$3$$$.
Since we can precompute all values of $$$\min(A_i,A_{i+1},\ldots,A_e)$$$ naively, we can do the transition of each state in $$$O(1)$$$.
In order to handle the events of type $$$2$$$, we can just write down the electricity fee for each elevator in each day. If that elevator is off on that day, we set the electricity fee of that elevator to be $$$\infty$$$.
Time complexity: $$$O(Q^3)$$$