22354번 - 돌 가져가기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 1450 | 413 | 366 | 30.099% |
문제
$N$ 개의 돌이 일렬로 나열되어 있다. 각 돌은 흰색 또는 검은색의 색상을 갖는다.
돌들을 왼쪽부터 1번 돌, 2번 돌,$\cdots$, $N$번 돌이라 하자. $i$번째 돌의 무게는 $A_i$이다.
당신은 나열된 돌들 중 하나를 골라 가져가는 것을 모든 돌이 없어질 때까지 총 $N$번 반복하려고 한다.
돌을 가져갈 때, 만약 그 돌이 현재 나열된 돌 중 가장 왼쪽이나 가장 오른쪽이 아니며, 가져간 돌에 인접한 두 돌 모두 가져간 돌과 다른 색인 경우 당신은 가져간 돌의 무게만큼의 점수를 얻는다.
가장 많은 점수를 얻을 수 있도록 돌을 가져가는 방법을 구하여라.
입력
첫 줄에 양의 정수 $N$이 주어진다. ($1 \le N \le 3 \times 10^5$)
둘째 줄에 B 또는 W로만 이루어진 길이 $N$의 문자열 $S$가 주어진다.
$S$의 $i$번째 문자 $S_i$는 왼쪽에서 $i$번째 돌의 색을 나타낸다. B는 돌이 검은색임을, W는 돌이 흰색임을 뜻한다.
셋째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 주어진다. ($1 \le A_i \le 10^9$)
$A_i$ 는 $i$번 돌의 무게를 나타낸다.
출력
첫째 줄에 최적의 방법으로 돌을 가져갔을 때 얻을 수 있는 점수를 출력한다.
예제 입력 1
8 WBBWBWBB 6 4 8 2 5 3 1 5
예제 출력 1
13
노트
처음 위치 기준 왼쪽에서 $5,\ 6,\ 2,\ 3,\ 4,\ 7,\ 8,\ 1$번째 돌을 순서대로 가져가면 $3$번째 돌과 $5$번째 돌을 가져갈 때 점수를 얻어 $13$점이 된다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호