혼돈 죽이기
시간 제한1초메모리 제한512 MB
주어진 순서대로 객차를 하나씩 폭파할 때, 각 시점에서 승객 수를 10의 배수로 올림한 값을 구간별로 더한 뒤 구간 수를 곱한 혼돈 값의 최댓값을 구한다.
문제
위험한 서부에서 강도들이 객차가 많은 긴 기차를 습격한다. 혼돈이 발생하는데, 강도들은 혼돈의 양이 기차에 있는 승객 수를 10의 배수로 올림한 값과 같다는 것을 깨닫는다. 혼돈을 가라앉히기 위해 그들은 객차 하나를 폭파해 승객 몇 명을 죽이기로 한다.
하지만 강도들이 미처 깨닫지 못한 것은, 서로 분리된 기차 구간이 여러 개 있을 때 전체 혼돈의 양은 각 기차 구간의 혼돈을 모두 더한 값에 기차 구간의 수를 곱한 값과 같다는 것이다!
더 심해진 혼돈을 가라앉히기 위해 허둥대던 강도들은 모든 승객이 죽을 때까지 모든 객차를 계속 폭파한다. 휴!
기차 구간의 혼돈은 그 기차 구간의 승객 수를 10의 배수로 올림한 값과 같다. 강도 행각 동안 발생한 혼돈의 최댓값은 얼마였을까?
입력
첫째 줄에 기차의 객차 수를 나타내는 정수 n이 주어진다. (3 ≤ n ≤ 100 000) 둘째 줄에 n개의 정수 p1, p2, . . . pn이 주어지는데, (각 i ∈ {1, 2, . . . , n}에 대해 0 ≤ pi ≤ 100) 이는 각 객차에 있는 승객 수이다. 셋째 줄이자 마지막 줄에 강도들이 객차를 폭파한 순서를 나타내는 1부터 n까지 수의 순열이 주어진다.
출력
강도 행각 동안 발생한 혼돈의 최댓값을 나타내는 정수 하나를 출력한다.