div2-1519-D-Maximum Sum of Products-dp

You are given two integer arrays a and b of length n.

You can reverse at most one subarray (continuous subsegment) of the array a.

Your task is to reverse such a subarray that the sum ∑ i = 1 n a [ i ] ⋅ b [ i ] \sum_{i=1}^na[i]⋅b[i]∑

i=1

n

a[i]⋅b[i] is maximized.

Input

The first line contains one integer n (1≤n≤5000).

The second line contains n integers a1,a2,…,an (1≤ai≤107).

The third line contains n integers b1,b2,…,bn (1≤bi≤107).

Output

Print single integer — maximum possible sum after reversing at most one subarray (continuous subsegment) of a.

Examples

inputCopy

5
2 3 2 1 3
1 3 2 4 2

outputCopy

29

inputCopy

2
13 37
2 4

outputCopy

174

inputCopy

6
1 8 7 6 3 6
5 9 6 8 8 6

outputCopy

235

Note

In the first example, you can reverse the subarray [4,5]. Then a=[2,3,2,3,1] and 2⋅1+3⋅3+2⋅2+3⋅4+1⋅2=29.

In the second example, you don’t need to use the reverse operation. 13⋅2+37⋅4=174.

In the third example, you can reverse the subarray [3,5]. Then a=[1,8,3,6,7,6] and 1⋅5+8⋅9+3⋅6+6⋅8+7⋅8+6⋅6=235.

当时hp了，没有想出来

首先处理出没有区间逆转的情况的前缀和，然后用dp[i][j]代表反转区间i -> j 之后的贡献

dp[l][r] == dp[l+1][r-1] + a[l] * b[r] + a[r] * b[l]，后面的两项为区间[l+1,r-1] 左右两侧的交叉相乘的结果

预处理出dp[i][i] == a[i] * b[i]

然后两层for循环枚举区间的起点 l 和终点 r

那么在区间为[l,r] 之间的贡献，总体的结果就是前面没有反转的部分加上后面没有反转的部分加上中间反转的部分，其中反转区间前后两段，我们已经在前面使用前缀和进行预处理，所以很容易就可以求出结果

int n,m,k;
ll a[maxn],b[maxn];
ll sum[maxn];
ll dp[5007][5007];
ll val(int l,int r){
    return sum[r] - sum[l-1];
}
int main() {
    n = read;
    for(itn i=1;i<=n;i++) a[i] = read;
    for(itn i=1;i<=n;i++) b[i] = read;
    for(int i=1;i<=n;i++){
        sum[i] = sum[i-1] + a[i] * b[i];
    }
    for(int i=1;i<=n;i++){
        dp[i][i] = a[i] * b[i];
    }
    for(int i=2;i<=n;i++){
        int l = 1;
        for(int r=i;r<=n;r++,l++){
            dp[l][r] = dp[l+1][r-1] + a[l] * b[r] + a[r] * b[l];
        }
    }
    ll ans = sum[n];
    for(itn i=1;i<=n;i++){
        for(itn j=i+1;j<=n;j++){
            ans = max(ans,dp[i][j] + val(1,i-1) + val(j+1,n));
        }
    }
    cout << ans <<endl;
    return 0;
}