블록 쌓기
시간 제한2초메모리 제한128 MB
격자에서 행별, 열별 최댓값 배열이 주어질 때 두 조건을 만족하는 배치가 가능한지 판단하고 가능한 블록 총합의 최소값과 최대값을 구합니다.
문제
가로 방향으로 N개의 위치, 세로 방향으로 M개의 위치가 있는 판에 단위 정육면체 블록을 쌓는다. 각 칸 (i, j)에 쌓인 블록의 높이를 H(i, j)라고 하자.
앞에서 보았을 때 왼쪽부터 i번째 위치의 높이는 A_i = max_j H(i, j)이고, 옆에서 보았을 때 j번째 위치의 높이는 B_j = max_i H(i, j)이다.
앞에서 본 높이 A와 옆에서 본 높이 B가 주어졌을 때, 두 모습과 모두 일치하도록 블록을 쌓을 수 있는지 판단하라. 가능하다면 필요한 블록 개수의 최솟값과 최댓값을 구하라.
입력
첫째 줄에 두 정수 N, M(1 ≤ N, M ≤ 100,000)이 주어진다.
이어지는 N개의 줄에는 앞에서 본 높이 A_1, ..., A_N이 왼쪽부터 차례대로 하나씩 주어진다. 그 다음 M개의 줄에는 옆에서 본 높이 B_1, ..., B_M이 차례대로 하나씩 주어진다.
모든 높이는 0 이상 2^31 - 1 이하의 정수다.
출력
두 모습과 일치하는 배치가 불가능하면 -1을 출력한다.
가능하면 한 줄에 가능한 최소 블록 수와 최대 블록 수를 공백으로 구분해 출력한다. 정답은 2^31 - 1을 넘지 않는다.