시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 180 | 22 | 15 | 12.195% |
《도미니언》의 확장판 《Dominion: Last Turn》은 매 턴마다 카드를 구매하여 덱을 구성하고 최후의 턴에 승점을 계산하는 게임입니다.
《도미니언》은 두 종류의 카드를 사용합니다. 하나는 행동 카드이며, 다른 하나는 승점 카드입니다. 행동 카드는 정수 $A$와 $B$가 새겨져 있으며, $A$번의 행동 횟수를 추가해 주고, $B$개의 카드를 뽑게 해 줍니다. 승점 카드에는 정수 $P$가 새겨져 있으며, 승점을 뜻합니다.
이러한 카드들을 한 턴에 하나씩 구매하여 덱을 만들고, 마지막 턴에는 아래와 같은 과정으로 승점을 계산합니다
유토는 이제 마지막으로 한 번의 구매 후 승점을 계산해야 합니다. 현재 유토의 덱과 구매할 수 있는 카드의 목록이 주어졌을 때 유토가 한 장을 덱에 추가한 후 얻을 수 있는 최대 승점을 알려주세요.
입력의 첫째 줄에는 현재 덱에 있는 카드의 수 $N$과 덱에 추가할 수 있는 카드의 종류 개수인 $M$이 공백으로 구분되어 주어집니다.
이후 $N$개의 줄에 걸쳐 덱에 있는 카드의 정보가 주어집니다.
이후 $M$개의 줄에 걸쳐 구매할 수 있는 카드의 정보가 주어집니다.
카드에 대한 정보는 카드가 행동 카드라면 Act
$A$ $B$ 의 형태로 주어지며, 승점 카드라면 Point
$P$ 의 형태로 주어집니다.
유토가 얻을 수 있는 최대 승점을 출력해주세요.
4 3 Act 1 1 Act 0 1 Point 5 Point 4 Point 1 Act 0 2 Act 1 1
9
유토는 Act
$0$ $2$ 의 카드를 구매합니다. 이후 덱을 Act
$1$ $1$, Act
$0$ $2$, Point
$4$, Point
$5$, Act
$0$ $1$ 순서로 정렬합니다. 유토가 Act
$1$ $1$ 카드와 Act
$0$ $2$ 카드를 사용한다면 손에 있는 카드는 Point
$4$, Point
$5$ 가 되고 최종 점수는 $4+5=9$가 됩니다. 어떠한 경우에도 이보다 높은 점수를 얻을 수는 없습니다.
2 2 Point 5 Point 4 Point 1 Point 6
6
9 2 Act 3 0 Act 0 2 Act 0 2 Act 0 2 Point 5 Point 4 Point 1 Point 1 Point 1 Act 0 2 Act 1 1
9
Contest > BOJ User Contest > 보드게임컵 > 보드게임컵 F번