시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 134 | 62 | 42 | 45.652% |
세계 정복의 야망을 품은 마왕은 자신의 국가를 만들기로 했다! 하지만 국가를 만들기 전, 영토를 정하거나 성을 세우는 등 해야 할 일이 많다.
영토가 될 수 있는 부지는 \(N \times M\)크기의 직사각형 모양이며, 부지는 \(1 \times 1\)단위 크기의 땅으로 나뉘어져 있다. 마왕은 하나 이상의 땅을 골라 자신의 영토로 선포하고, 그 중 하나의 땅에 마왕의 성을 세울 것이다. 각 땅에는 "땅의 높이"와 "얻을 수 있는 세금" 두 가지 수치가 정해져 있다. 다음 그림은 예제 2의 각 땅에서 얻을 수 있는 세금과 높이를 각각 나타낸 것이다.
마왕은 국민과의 소통을 중시하므로, 영토에 속하는 모든 땅은 상하좌우로 인접한 영토를 따라 이동해 마왕의 성에 도달할 수 있어야 한다. 또한 자신이 세상에서 가장 높은 사람이 되어야 한다는 확고한 철학이 있으므로, 마왕의 성을 세울 땅은 나머지 모든 영토의 높이보다 높거나 같아야 한다.
마왕이 얻을 수 있는 세금의 양은 영토에 포함된 각각의 땅에서 얻을 수 있는 세금의 합과 같다. 마왕은 \(N \times M\)개의 땅 각각에 성을 세울 때 최대 얼마 만큼의 세금을 얻을 수 있는지 알고 싶다. 하지만 마왕은 프로그래밍을 할 줄 모르기 때문에, 마왕에게 사로잡힌 여러분이 이 문제를 해결할 프로그램을 대신 작성해 보자.
첫째 줄에 영토가 될 수 있는 부지의 크기 $N$, $M$이 공백으로 구분되어 주어진다.
둘째 줄부터 $N$개의 줄에 걸쳐 ($i$, $j$)에 위치한 땅의 높이 $h_{ij}$가 $M$개씩 공백으로 구분되어 주어진다.
$N$ + 1번째 줄부터 $N$개의 줄에 걸쳐 ($i$, $j$)에 위치한 땅을 마왕의 영토로 만들 때 얻을 수 있는 세금 $c_{ij}$가 $M$개씩 공백으로 구분되어 주어진다.
$N$개의 줄에 걸쳐 각 위치에 마왕의 성이 있는 경우 영토를 적당히 선포하여 걷을 수 있는 세금의 합의 최댓값을 $M$개씩 공백으로 구분하여 출력한다.
3 4 1 1 7 4 3 1 2 2 4 5 3 6 1 1 1 1 1 1 1 1 1 1 1 1
3 3 12 9 7 3 5 5 9 10 7 11
3 3 1 2 1 3 10 4 1 5 1 2 9 4 6 16 9 14 11 6
2 15 4 35 77 50 14 61 6
University > 인하대학교 > 2023 인하대학교 프로그래밍 경진대회(IUPC) > Contest J번
University > 인하대학교 > 2023 인하대학교 프로그래밍 경진대회(IUPC) > Open Contest J번