No.1726 [Cherry 3rd Tune B] ジャマイカビアポン
タグ : / 解いたユーザー数 39
作問者 : 👑
Kazun
/ テスター :
tatyam
nebocco
問題文
座標平面上に (ビール入りの) コップが $N$ 個ある. ここで, $i~(1 \leq i \leq N)$ 番目のコップは座標 $(a_i, b_i)$ にあり, そして, 整数 $P_i$ が設定されている.
チェリーちゃんは $M$ 個のピンポン玉を投げるが, あなたが持っている予知能力により $j~(1 \leq j \leq M)$ 番目のピンポン玉は座標 $(c_j, d_j)$ に落ちることが分かっている. そして, ピンポン玉が落ちた座標にコップがあるとき, かつその時に限り, ピンポン玉はその座標のコップに入る.
あなたはチェリーちゃんが $M$ 個のピンポン玉を投げる前に, 以下の操作を $0$ 回以上任意の順に好きなだけ繰り返すことができる.
- ある実数 $p$ を選び, 全てのコップを直線 $x=p$ に関して対称な位置に移動させる.
- ある実数 $q$ を選び, 全てのコップを直線 $y=q$ に関して対称な位置に移動させる.
ここで, ピンポン玉が落ちる座標は操作の影響を受けない.
チェリーちゃんが $M$ 個のピンポン玉を投げた後, ピンポン玉が入っているコップに設定されている整数の総和が得点になる.
得点が最大になるように操作した場合の得点を求めよ.
制約
- $1 \leq N,M \leq 800$
- $-10^6 \leq P_i \leq 10^6$
- $-10^9 \leq a_i, b_i, c_j, d_j \leq 10^9$
- $i \neq i'$ ならば, $(a_i, b_i) \neq (a_{i'}, b_{i'})$
- $j \neq j'$ ならば, $(c_j, d_j) \neq (c_{j'}, d_{j'})$
- 入力は全て整数.
入力
入力は以下の形式で標準入力から与えられる.$N$ $M$ $P_1$ $\cdots$ $P_N$ $a_1$ $b_1$ $\vdots$ $a_N$ $b_N$ $c_1$ $d_1$ $\vdots$ $c_M$ $d_M$
出力
得点の最大値を整数で出力せよ. なお, 最後に改行をすること.
サンプル
サンプル1
入力
2 2 3 1 0 0 1 0 2 2 4 1
出力
3
2つのコップをそれぞれコップ A,B と呼ぶことにする. 以下のように3回操作をする
- $x=-2$ に関してコップを対称移動させる. コップ A は $(-4,0)$, コップ B は $(-5,0)$ に移動する.
- $y=\frac{1}{2}$ に関してコップを対称移動させる. コップ A は $(-4,1)$, コップ B は $(-5,1)$ に移動する.
- $x=0$ に関してコップを対称移動させる. コップ A は $(4,1)$, コップ B は $(5,1)$ に移動する.
このとき, チェリーちゃんが投げた $2$ つのピンポン玉のうち, $2$ 個目のピンポン玉はコップ A に入る. よって, 得点はコップ A に設定される整数が $3$ なので, $3$ 点になる.
また, どのように操作しても, 得点が $3$ 点より大きくなることはないので, $3$ が答えになる.
サンプル2
入力
3 3 100 20 3 0 0 -1 0 -1 1 0 0 1 0 1 1
出力
123
$x=0$ に関する対称移動を行うことで得点 $123$ 点を達成できる. また, 最初の状態で $(a_i, b_i)=(c_j, d_j)$ となるような整数 $i,j$ が存在するかもしれない.
サンプル3
入力
3 2 -1 -2 -4 1 1 2 4 3 9 4 16 5 25
出力
0
1つでもピンポン玉がコップに入ると, 得点が負になってしまう.
サンプル4
入力
20 24 -10 10 9 4 -3 10 7 4 6 -6 3 6 -10 3 1 -4 10 5 -10 -8 0 2 2 2 1 0 -1 -2 -1 -1 -2 -1 0 -1 0 -2 0 1 2 -1 1 2 2 1 -2 0 -2 2 0 0 1 1 2 0 1 -2 1 -1 -1 2 3 -1 3 1 2 2 1 3 -2 -2 -1 -2 -2 -1 -2 1 -1 1 3 -3 3 3 0 -2 0 1 2 -1 -1 -3 -2 -3 -1 3 -3 -1 0 0 2 -3 1 1 0 3 1 -2 -2 2
出力
56
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。