Tima10's blog

Find maximal possible value of (a[i] + a[j]) * (j — i)
By Tima10, history, 3 years ago, translation, In English

You are given n <= 1e6 numbers, all a[i] <= 1e6, among all pairs of indices (i, j), such that i != j you need to find the maximum value of (a[i] + a[j]) * (j — i). Only one solution involving something similar to D&C DP optimization is known to me, are there any other solutions?

  • Vote: I like it
  • +43
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

We can use bit mask dp also. Note (a[I]+a[j])<= $$$2*10^6$$$. We can fix this value and find max value of (j-i).

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain a bit please? How mask dp would work? and complexity of your program

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This problem. You can either read koosaga's editorial or ICPC 2017 problem D editorial (same problem).

→ Reply