问题1963--最大和(maxsum)

1963: 最大和(maxsum)

时间限制: 1 Sec  内存限制: 128 MB
提交: 84  解决: 35
[提交] [状态] [讨论版] [命题人:]

题目描述

我们考虑N个二元组(xi,yi),我们定义:
       newsum( {xi, yi} ) = sum ( xi*y(n+1-i) )
为了使得NewSum尽可能的大,我们要删去这个N个二元组的前B项和后H项。如:x={3,-4,-3,-2,2,0}   y={-3,0,5,-1,3,2} 
newsum {(xi,yi)} =3*2 + (-4)*3 + (-3)*(-1) + (-2)*5 + 2*0 + 0*(-3) = -13 
现在我们删去后面3个二元组,(前删去0个,也就是不删):
   x′={3,-4,-3}     y′={-3,0,5} 
newsum{(xi′,yi′)} =3*5+(-4)*0+(-3)*(-3)=24 
现在要求你求出这最大的NewSum。 

输入

第一行一个数N。 
下来两行,每行N个数字,分别是 xi和yi。

输出

第一行一个数,表示最大的NewSum的值。

样例输入 Copy

6 
3 -4 -3 -2 2 0
-3 0 5 -1 3 2

样例输出 Copy

24

提示

对于70%的数据,N≤100 
对于100%的数据,1≤N≤2000,数字在区间[-1000,1000]中。

来源/分类