Algebra Flash
Contest: Educational Codeforces Round 140 (Rated for Div. 2)
Difficulty rating: 2500
Tags: bitmasks, brute force, dp, graphs, math, meet-in-the-middle, trees

Huh, is that it? Slightly disappointed, you boot up the game and click on the new gamemode. It says "Colored platforms".

There are $$$n$$$ platforms, numbered from $$$1$$$ to $$$n$$$, placed one after another. There are $$$m$$$ colors available in the game, numbered from $$$1$$$ to $$$m$$$. The $$$i$$$-th platform is colored $$$c_i$$$.

You start on the platform $$$1$$$ and want to reach platform $$$n$$$. In one move, you can jump from some platform $$$i$$$ to platforms $$$i + 1$$$ or $$$i + 2$$$.

All platforms are initially deactivated (including platforms $$$1$$$ and $$$n$$$). For each color $$$j$$$, you can pay $$$x_j$$$ coins to activate all platforms of that color.

You want to activate some platforms so that you could start on an activated platform $$$1$$$, jump through some activated platforms and reach an activated platform $$$n$$$.

What's the smallest amount of coins you can spend to achieve that?

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le m \le 40$$$) — the number of platforms and the number of colors, respectively.

The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le m$$$) — the colors of the platforms.

The third line contains $$$m$$$ integers $$$x_1, x_2, \dots, x_m$$$ ($$$1 \le x_i \le 10^7$$$) — the cost of activating all platforms of each color.

Output format:
Print the smallest amount of coins you can spend to activate some platforms so that you could start on an activated platform $$$1$$$, jump through some activated platforms and reach an activated platform $$$n$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5 3
1 3 2 3 1
1 10 100

Example output:
11

Example input:
5 3
1 3 2 3 1
1 200 20

Example output:
21

Editorial:
Imagine we bought some subset of colors. How to check if there exists a path from $$$1$$$ to $$$n$$$?
Well, we could write an easy dp. However, it's not immediately obvious where to proceed from that. You can't really implement buying colors inside the dp, because you should somehow know if you bought the current color before, and that's not really viable without storing a lot of information.
Let's find another approach. Let's try to deduce when the subset is bad — the path doesn't exist. Trivial cases: $$$c_1$$$ or $$$c_n$$$ aren't bought. Now, if there are two consecutive platforms such that their colors aren't bought, the path doesn't exist. Otherwise, if there are no such platforms, you can show that the path always exists.
In particular, that implies that among all pairs of consecutive platforms, at least one color of the pair have to be bought. If the colors of the pair are the same, then it's just that this color have to be bought.
The next step is probably hard to get without prior experience. Notice how the condition is similar to a well-known graph problem called "vertex cover". That problem is about finding a set of vertices in an undirected graph such that all graph edges have at least one of their endpoints in the set. In particular, our problem would be to find a vertex cover of minimum cost.
That problem is known to be NP-hard, thus the constraints. We can't solve it in polynomial time but we'll attempt to it faster than the naive approach in $$$O(2^m \cdot m^2)$$$.
Let's start with this approach anyway. We can iterate over a mask of taken vertices and check if that mask is ok. In order to do that, we iterate over edges and check if at least vertex is taken for each of them.
Again, having a bit of prior experience, one could tell from the constraints that the intended solution involves meet-in-the-middle technique.
Let's iterate over the mask of taken vertices among vertices from $$$1$$$ to $$$\frac m 2$$$. Then over the mask of taken vertices from $$$\frac m 2 + 1$$$ to $$$m$$$. The conditions on edges split them into three groups: the edges that are completely in $$$\mathit{mask}_1$$$, the edges that are completely in $$$\mathit{mask}_2$$$ and the edges that have one endpoint in $$$\mathit{mask}_1$$$ and another endpoint in $$$\mathit{mask}_2$$$.
First two types are easy to check, but how to force the third type to be all good? Consider the vertices that are not taken into $$$\mathit{mask}_1$$$. All edges that have them as one of the endpoints will turn out bad if we don't take their other endpoints into $$$\mathit{mask}_2$$$. That gives us a minimal set of constraints for each $$$\mathit{mask}_1$$$: a mask $$$\mathit{con}$$$ that includes all vertices from the second half that have edges to at least one of non-taken vertex in $$$\mathit{mask}_1$$$.
Then $$$\mathit{mask}_2$$$ is good if it has $$$\mathit{con}$$$ as its submask. Thus, we would want to update the answer with the $$$\mathit{mask}_1$$$ of the minimum cost such that its $$$\mathit{con}$$$ is a submask of $$$\mathit{mask}_2$$$.
Finally, let $$$\mathit{dp}[\mathit{mask}]$$$ store the minimum cost of some $$$\mathit{mask}_1$$$ such that its $$$\mathit{con}$$$ is a submask of $$$\mathit{mask}$$$. Initialize the $$$\mathit{dp}$$$ with the exact $$$\mathit{con}$$$ for each $$$\mathit{mask}_1$$$. Then push the values of $$$\mathit{dp}$$$ up by adding any new non-taken bit to each mask.
When iterating over $$$\mathit{mask}_2$$$, check if it's good for edges of the second kind and update the answer with $$$\mathit{dp}[\mathit{mask}_2]$$$.
Overall complexity: $$$O(2^{m/2} \cdot m^2)$$$.