记录编号	3660	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]合并果子	最终得分	100
用户昵称	name:弓虽	是否通过	通过
代码语言	Pascal	运行时间	0.249 s
提交时间	2008-10-08 21:37:26	内存使用	0.19 MiB

program fruit(input,output);   
var  
 a:array [1..20000] of longint;   
 n,m,i,j,ans,x:longint;   
procedure work;   
var wi,wj,sum,wt,tn,x:longint;   
begin  
wi:=1;sum:=0;wj:=1;wt:=0;tn:=n;   
while sum<n-1 do  
begin  
inc(sum);   
a[tn+1]:=a[wj]+a[wj+1];   
x:=a[tn+1];   
a[wj]:=0;   
a[wj+1]:=0;   
ans:=ans+a[tn+1];   
wj:=wj+2;   
while a[wi]<a[tn+1] do  
inc(wi);   
for wt:=tn+1 downto wi+1 do  
a[wt]:=a[wt-1];   
a[wi]:=x;   
inc(tn);   
end;   
end;   
  
procedure pai(head,tail:longint);   
var  
 i,k,l,o:longint;   
begin  
 i:=head;   
 l:=tail;   
 k:=a[(i+l) div 2];   
   repeat  
   while a[i]<k do i:=i+1;   
    while a[l]>k do l:=l-1;   
     if i<=l then  
      begin  
       o:=a[i];   
       a[i]:=a[l];   
       a[l]:=o;   
       i:=i+1;   
       l:=l-1;   
      end;   
     until i>l;   
   if i<tail then pai(i,tail);   
   if head<l then pai(head,l);   
  end;   
  begin  
 assign(input,'fruit.in');   
 assign(output,'fruit.out');   
 reset(input);   
 rewrite(output);   
 readln(n);   
 for i:=1 to n do read(a[i]);   
  pai(1,n);   
  work;   
  write(ans);   
end.