D - DDPC特別ビュッフェ
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
A 君と B 君はDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦のDDPC特別ビュッフェを楽しんでいます。 A 君のトレーには N 個の料理が、 B 君のトレーは M 個の料理が置かれています。 A 君のトレーにある i 番目の料理の美味しさは A_iで、 B 君のトレーにある j 番目の料理の美味しさは B_j で表されます。
とっても仲良しな 2 人はより昼食を楽しむため、A 君のトレーにある料理 1 つと、 B 君のトレーにある料理 1 つを交換するという操作をちょうど K 回行うことにしました。 A 君のトレーにある料理の美味しさの総和が a で、 B 君のトレーにある料理の美味しさの総和が b で表されるとき、 2人の幸福度は a×b で表されます。
K 回交換を行ったあとのありうる幸福度のうち、最大の値を求めなさい。
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 A_2 … A_N B_1 B_2 … B_M
- 1 行目に A 君と B 君の持っている料理の数を表す整数 N, M (1≦N,M≦55) と料理の交換回数 K(1≦K≦999) が与えられる。
- 2 行目に A 君のトレーに置かれている i 番目の料理の美味しさを表す整数 A_i (0≦A_i≦22,222) が空白区切りで与えられる。
- 3 行目に B 君のトレーに置かれている j 番目の料理の美味しさを表す整数 B_j (0≦B_j≦22,222) が空白区切りで与えられる。
出力
ありうる 2 人の幸福度の最大値を 1 行に出力せよ。末尾の改行を忘れないこと。
部分点
この問題には部分点が設定されている。
- K=1 を満たすデータセットに正解した場合 10 点が与えられる。
- 0≦A_i,B_j≦55を満たすようなデータセットに正解した場合上記の部分点とは別に 20 点が与えられる。
- 追加制約のないデータセットに正解した場合さらに 70 点が得られ合計 100 点が得られる。
入力例 1
3 2 1 2 2 3 3 2
出力例 1
36
- A 君のトレーにある美味しさ 3 の料理と B 君のトレーにある美味しさ 2 の料理を交換すると 2 人の幸福度は 36 となり、これが最大の幸福度です。
入力例 2
3 2 2 2 2 2 3 3
出力例 2
36
- 1 回目の交換で A 君のトレーにある美味しさ 2 の料理と B 君のトレーにある美味しさ 3 の料理を交換し、 2 回目の交換で A 君のトレーにある美味しさ 3 の料理と B 君のトレーにある美味しさ 2 の料理を交換すると 2 人の幸福度は 36 となり、これが最大の幸福度です。