| Submit | All submissions | Best solutions | Back to list |
FIRING - Firing |
About N birds in a row, each bird i-th has power a[i]. If we shoot bird i-th, bird (i-1)-th, bird i-th and bird (i+1)-th will fight, so we lost a[i-1]+a[i]+a[i+1] energy (that a[0]=0, a[n+1]=0). And then, bird i+1 will stand near bird i-1.
John will shoot the bird in descending order of power. If at the time, we have many birds that power is maximum, Jonh'll shoot the bird i-th such that i is smallest possible. Let me know total energy John lost to shoot all bird.
Input
The first line is a integer: N. (1≤N≤1000000).
The next line is N integer: a[1],a[2],...,a[n]. (1≤a[i]≤1000000000).
Output
Only integer: Result.
Example
Input: 6
1 4 2 3 6 5
Output: 38
| Added by: | Phạm Bá Thái |
| Date: | 2013-10-21 |
| Time limit: | 1s-1.5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Mine |
hide comments
|
2014-12-08 12:37:35 Phạm Bá Thái
@Min_25 Yes, I see. But your solution is O(N.LogN) because you sorted. My solution did not sort, it's really O(N) :) |
|
|
2014-12-05 07:03:20 Min_25
@Phạm Bá Thái Thanks for updating. My solution shot the largest index in such a case. Last edit: 2014-12-05 07:08:48 |
|
|
2014-12-05 00:49:44 Phạm Bá Thái
Min_25's solustion was TLE :) |
|
|
2014-12-05 00:44:29 Phạm Bá Thái
Oh, yes. I edited my problem Thank @Min_25 so much Note: This problem can solve with O(n) |
|
|
2014-12-05 00:42:45 Min_25
@Phạm Bá Thái Perhaps, this problem is ambiguous. Input: 3 1 1 1 In that case, the total energy can be 5 or 6. So, we cannot output the answer uniquely. Please update the description. --ans(Francky)--> I can (as EB) update the description, if you please suggest it. @Francky Thank you. Since my solution has not got 100 points yet, I cannot determine the order of such cases. My solution assumed that the energy in the above case is 5. Last edit: 2014-11-07 05:25:00 |
RSS