決して難しい問題ではないのですが、
考え方と思わぬ落とし穴である意味感心してしまったので
今日はこの内容でいきたいと思います。
問題↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0260
まずはパッと見について。
ジョイントを使うか使わないか、という点で
「いかに計算量を少なくするかを問うているのではないか？」
と勝手に勘違いルートに誘導しているような感じがしました。
実際自分も見た瞬間（面倒なの来た）と思いました。
でも実際には給料の計算は”パイプの本数＊長さの総和”なので
一個ずつジョイントを付けていくとしたらでかい順でＯＫなんですよね。
今回作るときはその逆（1本のパイプをどんどん分離していく）でやってます。
あともう一つの落とし穴は値の大きさに関して。
パイプの本数は２～６５０００本、それら一つ一つの長さは１～１０００、
ジョイントは１～６４９９９本、それら一つ一つの長さは１～１０００なので、
最大のケースだとint型の表現できる範囲を軽く超えます。
なのであまり普段使わないlong型を使うという。
これに関しては本当にコンパイルエラーを食らったときは「えっ？」って思いました。
まあもちろん落ち着いて問題をよく読んでなかったのが原因なんですが。
問題を解く前にちゃんと細心の注意を払うべきですね。
結局はそうなんですが、いつもの悪い癖です。
* * * * * * * * * * * * * * * * * * * * * *
import java.util.Scanner;
import java.util.Arrays;
public class PCK201205 {
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int n;
long paipu,joint_sum,salary;
int[] joint;
while(true){
n=scan.nextInt();
if(n==0) break;
joint=new int[n-1];
paipu=0;
for(int i=0;i<n;i++){
paipu+=scan.nextInt();
}
joint_sum=0;
for(int i=0;i<n-1;i++){
joint[i]=scan.nextInt();
joint_sum+=joint[i];
}
Arrays.sort(joint);
salary=0;
for(int i=1;i<=n;i++){
if(2<=i){
joint_sum-=joint[i-2];
}
if(salary<(paipu+joint_sum)*i){
salary=(paipu+joint_sum)*i;
}
}
System.out.println(salary);
}
}
}