페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8140
서브태스크

에너지 교환 1s 1024MB

문제

N (1 \leq N \leq 2 \cdot 10^5)마리의 거북이들이 원형으로 배열되어 있다.

각 거북이는 자신의 등껍질에 숫자 a_i (1 \leq a_i \leq 10^9)만큼의 에너지를 보유하고 있다.
모든 거북이들은 처음에 에너지가 가득 차 있다.

매 분마다 거북이들은 문자열 s_1s_2 \dots s_N에 따라 에너지를 교환한다.

만약 i번 거북이가 에너지가 적어도 1만큼 있으면,
s_i가 'L'이라면 왼쪽에 있는 거북이에게 1만큼 에너지를 전달하고,
'R'이라면 오른쪽에 있는 거북이에게 1만큼 에너지를 전달한다.

모든 교환은 동시에 일어난다. 즉, 거북이가 가득 찬 에너지를 가지고 있어도 1만큼 주고, 또 1만큼 받으면 에너지를 그대로 보존한다.

만약 거북이의 에너지가 a_i를 초과하면 초과한 에너지는 사라진다.

정올이는 M분 후에 모든 거북이들 사이에 남아있는 에너지의 총합을 알고 싶어한다. (1 \leq M \leq 10^9)


입력

첫 번째 줄에는 N과 M이 주어진다.

두 번째 줄에는 거북이들의 에너지 이동 방향을 나타내는 문자열 s_1s_2 \dots s_N이 주어진다. 이 문자열은 'L'과 'R'로만 구성된다.

세 번째 줄에는 각 거북이의 에너지 용량을 나타내는 정수들 a_1, a_2, \dots, a_N이 주어진다.


출력

M분 후, 모든 거북이들 사이에 남아있는 에너지의 총합을 출력한다.

큰 정수들이 포함될 수 있기 때문에 64비트 정수 자료형을 사용해야 할 수도 있다.


부분문제

번호 점수 조건
#150점

N,M≤1000

#250점

추가 제약 조건 없음


예제 #1

3 1
RRL
1 1 1
2

거북이 2와 거북이 3은 서로 1만큼 에너지를 주고받아서 에너지가 보존된다. 거북이 1은 거북이 2에게 1만큼 에너지를 주지만, 거북이 2의 에너지 용량이 넘쳐서 1만큼의 에너지가 사라진다. 따라서 1분 후 남은 에너지의 총합은 2이다.


예제 #2

5 20
LLLLL
3 3 2 3 3
14

모든 거북이들은 왼쪽으로 1만큼 에너지를 주고받고, 오른쪽으로도 1만큼 주고받는다. 그래서 에너지는 시간이 지나도 모두 보존된다. 따라서 20분 후에도 에너지는 그대로 보존되어 14만큼 남는다.


예제 #3

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4
38

처음에 에너지는 총 51만큼 있지만, 5분 후 거북이 3, 6, 7번은 각각 5, 3, 5만큼 에너지를 잃게 되어 총 38만큼의 에너지가 남게 된다.



출처

USACO 2024 February Bronze 2번

로그인해야 코드를 작성할 수 있어요.