問題一覧 > 通常問題

No.2840 RGB Plates

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 : milkcoffee / テスター : suo 👑 ygussany
7 ProblemId : 11032 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-08-03 20:24:21

問題文

$N$ 個のりんごがあります。りんご $i$ の重さは $A_i$ です。また、$3$ 枚の皿があり、それぞれ赤, 緑, 青の色で塗られています。

あなたは $N$ 個全てのりんごを、それぞれ赤, 緑, 青のいずれか $1$ つの皿に乗せます。

赤, 緑, 青の皿に乗っているりんごの重さの和をそれぞれ $R,G,B$ として、以下の $2$ つの条件を満たすように乗せる必要があります。

  • どの皿にもりんごが $1$ 個以上乗っている。
  • $G=B$ である。

$R$ として考えられる最大値を求めて下さい。条件を満たすりんごの乗せ方が無い場合はそれを報告してください。

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

  • $3 \leq N \leq 3000$
  • $1 \leq A_i \leq 5000$
  • 入力は全て整数

出力

答えを整数で出力してください。 条件を満たすりんごの乗せ方が無い場合は -1 と出力してください。

サンプル

サンプル1
入力
5
1 2 3 4 5
出力
9

$5$ 個のりんごを乗せる皿をそれぞれ (緑, 緑, 青, 赤, 赤) とすると、 $G=B=3$ となり、$R=9$ となります。

条件を満たす乗せ方では $R$ は $9$ が最大です。

サンプル2
入力
3
1 2 3
出力
-1

どの皿にもりんごが $1$ 個以上乗っている必要があります。$G=B$ の条件を満たすりんごの乗せ方はありません。

サンプル3
入力
11
59 927 349 933 1451 453 2000 975 345 782 123
出力
4733

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。