Hints: https://atcoder.jp/contests/arc176/editorial/9845

We formulate the problem as a minimum cut in a graph. Hereafter, let \(P = \max A = 500\).

First, prepare a source \(S\) and a sink \(T\). Then, for each \(X_i\), prepare vertices \(U_{i,1},U_{i,2},\dots,U_{i,P}\). Then, add the following edges. (\(U_{i,P+1}\) refers to \(S\).)

• An edge from \(U_{i,j+1}\) to \(U_{i,j}\) with cost \(j\) \((1 \le j \le P)\)
• An edge from \(U_{i,j}\) to \(U_{i,j+1}\) with cost \(\infty\) \((1 \le j \le P)\)
• An edge from \(U_{i,X_i}\) to \(T\) with cost \(\infty\)

Here, the assignment of \(U_i\) is such that \(U_{i,m},U_{i,m-1},...,U_{i,k+1}\) are on the \(S\) side, and \(U_{i,k},U_{i,k-1},\dots,U_{i,1}\) are on the \(T\) side. This cut corresponds to eventually setting \(X_i = k\). Similarly, prepare vertices \(V_{i,1},V_{i,2},\dots,V_{i,m}\) for \(Y_i\) and add edges. (Note that the direction of the edges will be reversed.)

Prepare a vertex \(W_i\) that represents whether to operate the integer sequence \(A_i\) on \(X\) or \(Y\). Here, placing \(W_i\) on the \(T\) side corresponds to operating \(A_i\) on \(X\), and placing it on the \(S\) side corresponds to operating \(A_i\) on \(Y\). This can be achieved by adding edges as follows.

• An edge from \(U_{j,A_{i,j}}\) to \(W_i\) with cost \(\infty\)
• An edge from \(W_i\) to \(V_{j,A_{i,j}}\) with cost \(\infty\)

Therefore, it can be seen that the minimum cut of the above graph is the answer. Since the minimum cut equals maximum flow, we should find the maximum flow in this graph.

By the way, the answer to this problem is at most \(2NP\). Thus, the flow is at most \(2NP\), and the computational complexity of the Dinic’s algorithm is \(\mathrm{O}(F \times E)\) (\(F\) is the flow, \(E\) is the number of edges), so this problem can be solved in \(\mathrm{O}(N^2P(M+P))\).

Sample Implementation