Colouring a rectangle
시간 제한2초메모리 제한512 MB
m x n 격자의 오른쪽 아래 방향 대각선과 오른쪽 위 방향 대각선마다 비용이 주어질 때, 모든 칸을 덮는 대각선을 최소 비용으로 고른다. 그 최소 비용을 출력한다. 이때 칸은 여러 번 칠해도 된다. (전체를 160자 이내로 요약) Either rephrase this in Korean concisely. Let me recount: Maybe Korean summary can be shorter. Let's craft:
문제
Srečko would like to paint a rectangular grid having m rows (numbered from 0 to m-1) and n columns (numbered from 0 to n-1). Initially, all cells in the grid are white. In each step, he chooses a diagonal and paints all of its cells using his favourite colour. However, some diagonals may be more expensive to paint than others, regardless of their length. Given the cost of painting each of the diagonals, write a program to tell Srečko the minimum total cost of painting all cells in the grid. Note that cells can be painted twice.
A rectangular grid with m rows and n columns has 2m + 2n - 2diagonals. For instance, if m = 4 and n = 3, there are 12 diagonals:
입력
The input consists of three lines.
The first line contains the numbers m and n.
The second line contains m + n - 1 numbers that specify the costs of painting the diagonals running in the ↘ direction. The i-th number (for i ∈ {1, ..., m + n - 1) refers to the diagonal in which the difference between the row index and the column index is i - n. The first number thus refers to the diagonal that consists only of the cell (0, n-1) (row 0, column n-1), the second number refers to the diagonal comprising the cells (0, n-2) and (1, n-1), etc. The order of the diagonals is thus the same as in the first row of the above figure.
The third line contains m + n - 1 numbers that specify the costs of painting the diagonals running in the ↗ direction. The i-th number (for i ∈ {1, ..., m + n - 1}) refers to the diagonal in which the sum of the row index and the column index is i - 1. The first number thus refers to the diagonal that consists only of the cell (0, 0), the second number refers to the diagonal comprising the cells (1, 0) and (0, 1), etc. The order of the diagonals is thus the same as in the second row of the above figure.
출력
Output the minimum cost of painting the grid.
제한
- 1 ≤ m ≤ 2·105
- 1 ≤ n ≤ 2·105
- The costs are integers from the interval [1,109]