Killing Chaos
Time limit1sMemory limit512 MB
Coaches are destroyed one by one in a given order; after each destruction, report the maximum total chaos over the whole process, where chaos sums rounded-up segment counts times the number of segments.
- Level
Medium7 of 10
- Topics
- Union-find, Implementation, Array, Math
- Solved
- No attempts yet
Problem
In the dangerous wild west, robbers attack a long train with many coaches. Chaos erupts, and the robbers realize that the amount of chaos equals the number of passengers in the train rounded up to the nearest multiple of 10. To quench the chaos, they therefore decide to kill some passengers by blowing up one of the coaches.
What the robbers failed to realize, however, is that when there are multiple disjoint train segments, the total amount of chaos equals the sum of the chaos of each train segment times the number of train segments!
Frantic to quench the now even worse chaos, the robbers continue blowing up every coach until all passengers are dead. Phew!
The chaos in a train segment is equal to the number of passengers in that train segment rounded up to the nearest multiple of 10. What was the maximum amount of chaos during the robbery?
Input
On the first line is a single integer n, (3 ≤ n ≤ 100 000), the number of coaches in the train. On the second line follow n integers p1, p2, . . . pn, (0 ≤ pi ≤ 100 for each i ∈ {1, 2, . . . , n}), the number of passengers in each coach. On the third and final line follows a permutation of the numbers from 1 to n indicating the order in which the robbers blew up the coaches.
Output
A single integer, the maximum chaos that occurred during the robbery.