Here we go again...

[Nineshadow]

@fizzlesticks Hello there. I know you like these <3.

 

Let S be an array ( a₁, a₂ , a₃ , .. , a_n ) of n natural numbers.

Considering a not null sequence of the form a_i , a_i+1 , ... ,a_j-1 , a_j , we say that its associated cost is equal to h*(j - i + 1) , where h is the minimum value in the sequence.

For example :

S = { 1 , 9 , 7 , 8 , 1 }

The sequence { 7 , 8 , 1 } has a cost = 1 * 3 = 3 .

 

Given a number n and an array of n numbers , calculate the maximum cost which can be obtained by any subsequence of the given array.

 

Example :

• input :

5
1 9 7 8 1

• output :

21

• The sequence with a maximum cost is :

{ 9 , 7 , 8 }

 

Restrictions :

• time : 0.1 sec
• memory : 16384 kbytes
• n <= 200 000
• each element of the array is smaller than 1 000 000 000

 

I've implemented a very obvious solution ( calculating the cost for each possible subsequence ) , and that one got 20% of the tests ( exceeded the execution time) . Not as bad as I expected. Anyway , I've been thinking of something about dynamic programming or maybe binary indexed trees. But as usual , the solution is going to be something really easy and obvious , but which I just didn't think about. Probably.

[fizzlesticks]

 

6 hours ago, Nineshadow said:

@fizzlesticks Hello there. I know you like these <3.

Ah yes that's a mighty fine lookin problem you've got there.  And I have no idea how to solve it.

 

But my brute force method got 30% so that's something.

[Philosobyte]

7 hours ago, Nineshadow said:

snip

Please link (I haven't had luck searching infoarena since it's in a foreign language). I have ideas, but this time I'm not going to pollute the thread with junk until I get 100%. 

[fizzlesticks]

4 minutes ago, Philosobyte said:

Please link (I haven't had luck searching infoarena since it's in a foreign language). I have ideas, but this time I'm not going to pollute the thread with junk until I get 100%. 

http://www.infoarena.ro/problema/strabunica