Ahnaf.Shahriar.Asif's blog

By Ahnaf.Shahriar.Asif, history, 7 years ago, In English

everything seems okay , where is the problem ? can you explain ? problem link : http://codeforces.net/contest/855/problem/B

my code : https://paste.ubuntu.com/25608466/

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

consider this input: 3 1 1 -1 -1 100 1000

should output: 1000

your solution: -1

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As I told you before, greedy approach will not work here.

You can try Dynamic programming to solve this type of problem where greedy doesn't work. But for this there is a brute force solution.

for each number in the array, let's say that this is aj and we multiply it with q. So we are fixing the middle element every time. Now we have to find ai and ak [i ≤ j and j ≤ k] such that ai * p + ak * r is maximized. So we can easily get an O(n2) solution. How to make it O(n)? Well the array is static. So we can pre-calculate the minimum and maximum in each suffix and prefix of the array and use them instead of running a loop each time to find ai and ak. This is the same solution described in the editorial btw.