Balatro

시간 제한12초메모리 제한1024 MB

요약

덧셈 카드와 곱셈 카드가 한 줄로 놓여 있을 때, 곱셈 카드를 k장 이하로 골라 최종 점수가 최대가 되는 부분수열을 길이별로 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 정렬, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

카드 여러 장이 한 줄로 놓여 있다. 각 카드는 값을 가지며, 덧셈 카드(a)와 곱셈 카드(m) 중 하나이다.

점수는 다음과 같이 계산한다. 처음 점수는 0이다. 카드를 왼쪽부터 차례로 처리한다.

덧셈 카드이면 점수에 카드의 값을 더한다.
곱셈 카드이면 점수에 카드의 값을 곱한다.

모든 카드를 처리한 뒤의 점수가 최종 점수이다.

부분 수열의 크기마다, 그 크기의 부분 수열에서 얻을 수 있는 최대 점수를 구한다. 곱셈 카드 개수의 상한 때문에 해당 크기를 만들 수 없으면, 그보다 작은 크기 중 만들 수 있는 가장 큰 크기의 최대 점수를 구한다. 고른 카드는 원래 순서를 유지하며, 순서를 바꿀 수 없다. 부분 수열은 연속일 필요가 없다.

입력

첫 줄에 두 정수 $n$ ( $2≤n≤2 \cdot10^5$ )과 $k$ ( $0≤k≤n$ )이 주어진다. $n$ 은 카드의 개수이고, $k$ 는 사용할 수 있는 곱셈 카드의 최대 개수이다.

다음 $n$ 개의 줄에는 문자 $s$ 와 정수 $v$ 가 주어진다. $s$ 는 a(덧셈 카드) 또는 m(곱셈 카드)이며, $v$ 는 카드의 값이다 ( $2≤v≤1\,000$ ).

모든 곱셈 카드 값의 곱은 $10^9$ 이하이다.

출력

$n$ 개의 줄을 출력한다. $i$ 번째 줄에는 길이가 $i$ 이하인 부분 수열에서 얻을 수 있는 최대 점수를 출력한다. $i$ 는 1부터 $n$ 까지이다.

예제2

예제 1
입력
```
4 3
a 3
m 2
a 8
m 3
```
예상 출력
```
8
24
33
42
```

예제 2

입력

6 1
a 2
m 5
a 2
a 2
m 3
a 3

예상 출력