1519D.md (1435B)
1 Source: https://codeforces.com/problemset/problem/1519/D 2 3 D. Maximum Sum of Products 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two integer arrays $a$ and $b$ of length $n$. 22 23 You can reverse at most one subarray (continuous subsegment) of the array $a$. 24 25 Your task is to reverse such a subarray that the sum $\sum\limits_{i=1}^n a_i \cdot b_i$ is maximized. 26 27 Input 28 29 The first line contains one integer $n$ ($1 \le n \le 5000$). 30 31 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^7$). 32 33 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^7$). 34 35 Output 36 37 Print single integer — maximum possible sum after reversing at most one subarray (continuous subsegment) of $a$. 38 39 Examples 40 41 Input 42 43 ``` 44 5 45 2 3 2 1 3 46 1 3 2 4 2 47 ``` 48 49 Output 50 51 ``` 52 29 53 ``` 54 55 Input 56 57 ``` 58 2 59 13 37 60 2 4 61 ``` 62 63 Output 64 65 ``` 66 174 67 ``` 68 69 Input 70 71 ``` 72 6 73 1 8 7 6 3 6 74 5 9 6 8 8 6 75 ``` 76 77 Output 78 79 ``` 80 235 81 ``` 82 83 Note 84 85 In the first example, you can reverse the subarray $[4, 5]$. Then $a = [2, 3, 2, 3, 1]$ and $2 \cdot 1 + 3 \cdot 3 + 2 \cdot 2 + 3 \cdot 4 + 1 \cdot 2 = 29$. 86 87 In the second example, you don't need to use the reverse operation. $13 \cdot 2 + 37 \cdot 4 = 174$. 88 89 In the third example, you can reverse the subarray $[3, 5]$. Then $a = [1, 8, 3, 6, 7, 6]$ and $1 \cdot 5 + 8 \cdot 9 + 3 \cdot 6 + 6 \cdot 8 + 7 \cdot 8 + 6 \cdot 6 = 235$.