BOI7SEQ - Sequence
We are given a sequence a1 , ..., an . We can manipulate this sequence using the operation reduce(i), which replaces elements ai and ai+1 with a single element max(ai , ai+1 ), resulting in a new shorter sequence. The cost of this operation is max(ai , ai+1 ). After n−1 operations reduce, we obtain a sequence of length 1. Our task is to compute the cost of the optimal reducing scheme, i.e. the sequence of reduce operations with minimal cost leading to a sequence of length 1.
The first line contains n (1 ≤ n ≤ 1,000,000), the length of the sequence. The following n lines contain one integer ai , the elements of the sequence (0 ≤ ai ≤ 1,000,000,000).
In the first and only line of the output print the minimal cost of reducing the sequence to a single element.
Frustrating to crack, and in the end the stupid time limit makes this an input test: TLE in PyPy, 0.01s in CPP.
Good question !!!
I am getting correct output for all test cases at spojtoolkit.com yet my solution is not getting acceptedLast edit: 2018-07-07 21:02:30
Don't be a fool. The input is NOT sorted always.
@akshayvenkat where is it specifed?
the input seems to be sorted always
O(n) in java cannot pass, just need 0.5s more :(((