\(M\) 回の操作を行い、\(i\) 回目の操作で \(X_i, Y_i\) が書かれたボールを食べるとして、得られる点数は \(\sum_{i=1}^M X_i Y_i + \sum_{i=1}^M C_i \cdots (1)\) と書けます。この値は操作順によらないことに注意してください。

赤いボールのうち最大の整数が書かれているのが \(i\) 番目、青いボールのうち最大の整数が書かれているのが \(j\) 番目であるとき、次が成り立ちます。

• 赤いボール \(i\) と青いボール \(k (\neq j)\)、赤いボール \(l (\neq i)\)と青いボール \(j\) をそれぞれ同時に食べる場合、代わりに赤いボール \(i\) と青いボール \(j\)、赤いボール \(l\) と青いボール \(k\) をそれぞれ同時に食べることにすると、\((A_i B_j + A_l B_k) - (A_i B_k + A_l B_j) = (A_i - A_l)(B_j - B_k) \geq 0\) 点だけ得である。\(\cdots (2)\)

さらに、赤いボール \(i\) と青いボール \(j\) に書かれた整数が共に非負であるとき、以下が成り立ちます。

• 赤いボール \(i\) と青いボール \(k (\neq j)\) を同時に食べ、青いボール \(j\) は食べない場合、代わりに赤いボール \(i\) と青いボール \(j\) を同時に食べ、青いボール \(k\) は食べないことにすると、\(A_i B_j - A_i B_k = A_i(B_j - B_k) \geq 0\) 点だけ得である。
• 赤いボール \(l (\neq i)\)と青いボール \(j\) を同時に食べ、赤いボール \(i\) は食べない場合、代わりに赤いボール \(i\) と青いボール \(j\) を同時に食べ、赤いボール \(l\) は食べないことにすると、\(A_i B_j - A_l B_j = (A_i - A_l)B_j \geq 0\) 点だけ得である。
• 赤いボール \(i\) も青いボール \(j\) も食べず、それ以外に \(M'\) 回操作を行う場合、追加で赤いボール \(i\) と青いボール \(j\) を同時に食べることにすると、\(A_i B_j + C_{M'+1} \geq 0\) 点だけ得である。

したがって、ここまでの条件を満たす赤いボール \(i\) と青いボール \(j\) は必ず同時に食べて損をしないため、これらを食べてしまった上でサイズの小さい問題を解けばよいです。これを可能な限り繰り返します。

ところで、全てのボールに書かれている整数の符号を反転させても答えは変わりません。符号反転ののちに以上のことをもう一度行うと、赤いボールと青いボールのうち一方は正のみ、もう一方は負のみになります。

操作回数 \(M\) を固定すると、 \((1)\) の第二項は定数になります。第一項の積は必ず負になるため、なるべくこの減少分を小さくすることを考えます。まず、\(A, B\) を あらかじめ絶対値の昇順にソートしておくと、それぞれ用いるべきは先頭 \(M\) 項になります。そして、\((2)\) の考え方により、残っている中で最大のもの同士を同時に食べていけばよいです。したがって、\((1)\) の第一項の最適値は \(\sum_{i=1}^M A_i B_{M - i + 1}\) となります。各 \(M\) について以上の計算を愚直に行って最大値を求めるアルゴリズムは \(O(N^2)\) の計算量で動作し、部分点が得られます。

ここで、最適値は畳み込みの形になっているので、高速フーリエ変換を用いて各 \(M\) についての値が一度に得られます。大きめの整数をそのまま扱うことになるので、AC Library の convolution_ll などを用いるとよいです。計算量は \(O(N \log N)\) となり、これで満点が得られます。

原案: packer_jp

改題: carrot46