记录编号	11593	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]合并果子	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.098 s
提交时间	2009-08-12 21:50:12	内存使用	0.19 MiB

program fuckruit;
var
  i,n:longint;
  t1,t2,tmp,sum:int64;
  fruit:array [0..10000] of int64;
procedure keepheap(node:longint);
var tmp,l,r,min:longint;
begin
  l:=node*2;r:=l+1;min:=node;
  if (l<=n) and (fruit[l]<fruit[min]) then min:=l;
  if (r<=n) and (fruit[r]<fruit[min]) then min:=r;
  if min<>node then begin
    tmp:=fruit[node];
    fruit[node]:=fruit[min];
    fruit[min]:=tmp;
    keepheap(min);
  end;
end;
function getmin:int64;
begin
  getmin:=fruit[1];
  fruit[1]:=fruit[n];
  dec(n);
  keepheap(1);
end;
begin
  fillchar (fruit,sizeof(fruit),0);
  assign (input,'fruit.in');
  reset (input);
  assign (output,'fruit.out');
  rewrite (output);
  readln (n);
  for i:=1 to n do read (fruit[i]);
  close (input);
  for i:=n div 2 downto 1 do keepheap(i);
  sum:=0;
  while n<>1 do begin
    t1:=getmin;
    t2:=getmin;
    sum:=sum+t1+t2;n:=n+1;
    fruit[n]:=t1+t2;
    i:=n;
    while (i>1) and (fruit[i div 2]>fruit[i]) do begin
      tmp:=fruit[i div 2];
      fruit[i div 2]:=fruit[i];
      fruit[i]:=tmp;
      i:=i div 2;
    end;
  end;
  writeln (sum);
  close (output);
end.