ヒント \(\rightarrow\) https://atcoder.jp/contests/arc176/editorial/9825

問題をグラフの最小カットで定式化します。以下、\(P = \max A = 500\) とします。

まず、始点 \(S\) と終点 \(T\) を用意します。そして \(X_i\) に対して頂点 \(U_{i,1},U_{i,2},\dots,U_{i,P}\) を用意します。このとき、以下のように辺を貼ります。(ただし、\(U_{i,P+1}\) は \(S\) を指します。)

• \(U_{i,j+1} \rightarrow U_{i,j}\) にコスト\(j\) の辺\((1 \le j \le P)\)
• \(U_{i,j} \rightarrow U_{i,j+1}\) にコスト \(\infty\) の辺\((1 \le j \le P)\)
• \(U_{i,X_i} \rightarrow T\) にコスト \(\infty\) の辺

このようにすると、\(U_i\) の割り当ては \(U_{i,m},U_{i,m-1},...,U_{i,k+1}\) が \(S\) 側、\(U_{i,k},U_{i,k-1},\dots,U_{i,1}\) が \(T\) 側という形になります。このカットを、最終的に \(X_i = k\) にすることと対応させます。同様に、\(Y_i\) についても頂点 \(V_{i,1},V_{i,2},\dots,V_{i,m}\) を用意して辺を貼ります。(辺の向きが入れ替わることに注意してください。)

整数列 \(A_i\) を \(X,Y\) のどちらに操作するかを意味する頂点 \(W_i\) を用意します。ここで、\(W_i\) を \(T\) 側にすることを \(A_i\) を \(X\) に操作することに、\(S\) 側にすることを \(A_i\) を \(Y\) に操作することに対応させます。これは、以下のように辺を貼ることで達成できます。

• \(U_{j,A_{i,j}} \rightarrow W_i\) にコスト \(\infty\) の辺
• \(W_i \rightarrow V_{j,A_{i,j}}\) にコスト \(\infty\) の辺

よって、上記のグラフの最小カットが答えとなることが分かりました。最小カット \(=\) 最大流なので、このグラフの最大流を求めればよいです。

ところで、この問題の答えは高々 \(2NP\) です。よって流量は最大でも \(2NP\) であり、dinic 法の計算量は \(\mathrm{O}(F \times E)(F\) は流量、\(E\) は辺の本数)なのでこの問題を \(\mathrm{O}(N^2P(M+P))\) で解くことが出来ます。

実装例