배열 B의 값
면접 대비시간 제한2초메모리 제한512 MB
N×M 배열에서 행 한 쌍 또는 열 한 쌍을 최대 한 번 바꿔 모든 2×2 블록 합의 총합이 최대가 되도록 만든다.
문제
크기가 N×M인 배열 A가 있을 때, 다음과 같은 방법으로 크기가 (N-1)×(M-1)인 배열 B를 만들 수 있다.
- B[i][j] = A[i][j] + A[i+1][j] + A[i+1][j+1] + A[i][j+1] (1 ≤ i < N, 1 ≤ j < M)
배열의 값은 배열의 모든 원소를 합한 값이다.
배열 A에서 임의의 두 행이나 임의의 두 열의 위치를 교환할 수 있다. 배열 A에서 교환을 최대 1번 수행해서 만들 수 있는 배열 B의 값의 최댓값을 구해보자.
입력
첫째 줄에 배열 A의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 배열의 원소가 주어진다. 배열은 정수로만 이루어져 있다.
출력
만들 수 있는 배열 B의 값 중 최댓값을 출력한다.
제한
- 2 ≤ N, M ≤ 1,000
- -1,000 ≤ Ai,j ≤ 1,000