练一下斜率优化

1 var s1,s2,f:array[0..1000010] of int64; 2     q,a,b:array[0..1000010] of longint; 3     i,n,h,t,j:longint; 4  5 function g(j,k:longint):double; 6   var a,b:double; 7   begin 8     a:=f[j]-f[k]-s2[j]+s2[k]; 9     b:=s1[k]-s1[j];10     exit(a/b);11   end;12 13 begin14   readln(n);15   for i:=1 to n do16     read(a[i]);17   for i:=1 to n do18   begin19     read(b[i]);20     s1[i]:=s1[i-1]+b[i];21     s2[i]:=s2[i-1]+int64(b[i])*int64(n-i+1);22   end;23   h:=0;24   t:=0;25   for i:=1 to n do26   begin27     while (h
      
       =n-i+1) do inc(h);28     j:=q[h];29     f[i]:=f[j]+a[i]+s2[i-1]-s2[j]-(s1[i-1]-s1[j])*int64(n-i+1);30     while (h
       
        =g(q[t-1],q[t])) do dec(t);31     inc(t);32     q[t]:=i;33   end;34   writeln(f[n]);35 end.