| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
You have two arrays A and B. They have the same length and values are from positive integers. For example:
A = [6, 3, 4, 8, 3] B = [2, 4, 2, 1, 2]
You need to find such two indexes i, j where i != j such that expression A[i] * B[i] + A[i] * B[j] + A[j] * B[j] is maximized. For example here it is i = 3, j = 1 which gives maximum of 52
I will assume that $$$i < j$$$ in this explanation. The other case is symmetric, so I will not explain it.
Now we go and process indices $$$j$$$ from first to last. For each index, we will find the optimal i and calculate the value of the function. How do we find the optimal $$$i$$$ though?
For all indices $$$i$$$ ($$$1 \le i < j$$$) we will put a function $$$f_i(x) = A_i \cdot x + A_i \cdot B_i$$$ in some container. Now values of picking current $$$j$$$ and some $$$i$$$ is $$$f_i(B_j) + A_j \cdot B_j$$$. As the second part is constant, we are only interested in finding the function with maximal value. Then we evaluate the expression, update our maximum, add function $$$f_j(x) = A_j \cdot x + B_j \cdot A_j$$$ into the container, and move on to the next $$$j$$$.
Now you might wonder how you add functions and find the maximal value fast. Well, you can use Li Chao Tree.
Time complexity is $$$O(N log N)$$$.
Not sure if there is a simpler way than using Li Chao, but this is the first solution that comes to my mind.