시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 822 | 314 | 241 | 40.572% |
지우고 싶은 문자열 $S$와 지울 수 있는 문자열 $A_{1}$, $A_{2}$, ..., $A_{M}$이 주어진다. 문자열 $A_{i}$들은 각자 $X_{i}$라는 점수를 가진다. 이 때, 문자열 $S$를 삭제 연산을 이용하여 모두 제거하려고 한다.
삭제 연산은 두 가지 방법이 존재하며, 원하는 만큼 여러 번에 걸쳐서 수행할 수 있다.
예를 들어, 문자열 $S$가 "abcxyzxabc
"이 있고 "abc
" 문자열을 지울 경우 10점, "xyz
" 문자열을 지울 경우 5점을 얻는다고 하자. 문자열을 모두 제거하여 최대 점수를 얻을 수 있는 과정은 아래와 같다.
xyz
" 하나를 지운다. 현재 총 얻은 점수는 5점이고 문자열 $S$는 "abc___xabc
"가 된다. 이때, '_
'는 문자가 지워진 자리를 의미한다.abc
" 하나를 지운다. 현재 총 얻은 점수는 15점이고 문자열 $S$는 "______xabc
"가 된다.abc
" 하나를 지운다. 현재 총 얻은 점수는 25점이고 문자열 $S$는 "______x___
"가 된다.문자열을 모두 제거하여 얻을 수 있는 최대 점수는 26점이다. 이보다 더 얻을 수 있는 점수는 없다.
삭제 연산을 이용하여 문자열 $S$을 지울려고 할 때 얻을 수 있는 최대 점수는 몇 점인지 계산하자.
첫번째 줄에는 문자열 $S$이 주어진다.
두번째 줄에는 지울 수 있는 문자열 개수 $M$이 주어진다.
세번째 줄부터 $M + 2$ 줄까지 문자열 $A_{i}$와 점수 $X_{i}$이 공백으로 구분되어 주어진다.
문자열 $S$를 모두 제거하여 얻을 수 있는 점수를 출력하자.
abcxyzxabc 2 abc 10 xyz 5
26
abcxyzxabc 2 abc 2 xyz 1
10