Блог пользователя Tima10

Find maximal possible value of (a[i] + a[j]) * (j — i)
Автор Tima10, история, 3 года назад, По-русски

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 others?

  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится -23 Проголосовать: не нравится

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).

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить