시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)38181645.714%

문제

이 문제는 패널 최적화(Easy)와 $N$ 제한만 다른 상위 문제이고, 패널 최적화(Easy)에 이 문제의 정답 코드를 제출하여 맞힐 수 있다.

근수의 태양광 패널은 $N \times N$ 크기의 격자판으로 이루어져 있다. $(i, j)$에 위치한 격자의 초기 전압은 $A_{ij}$로 주어지며, 이 격자의 전압을 $1$씩 증가시키거나 감소시킬 때 마다 $B_{ij}$만큼의 에너지가 소모된다.

근수는 초기에 $0$의 에너지를 가지고 있다. 근수는 현재 에너지의 값과 관계없이 각 격자의 전압을 원하는 만큼 올리거나 낮출 수 있다. 격자의 전압 조정이 끝나면, 격자판에서 인접한 두 격자들 간의 전압 상태에 따라 에너지를 얻거나 잃을 수 있다. 여기서 인접한 격자는 상하 좌우로 연결된 격자를 의미한다.

에너지는 다음과 같은 조건에 따라 얻거나 잃는다.

  • 두 인접한 격자의 전압 부호가 한쪽이 양수이고 다른 한쪽이 음수면 두 격자 간의 에너지 흐름이 만들어져서 최종 에너지가 $4K$만큼 올라간다.
  • 한 격자의 전압이 $0$이고 다른 격자의 전압이 양수 또는 음수일 경우에는 아무 일도 일어나지 않는다.
  • 두 격자의 전압이 모두 $0$이면, 두 격자는 방전되기 시작하여서 최종 에너지가 $2K$만큼 줄어든다.
  • 두 인접한 격자의 전압 부호가 둘 다 양수거나 둘 다 음수면 두 격자가 서로 과부하 되어서 최종 에너지가 $4K$만큼 줄어든다.

즉 두 격자의 전압 부호에 따른 에너지 변화는 다음과 같다.

근수의 목표는 격자판들의 전압을 잘 조절하여 최종 에너지를 최대화하는 것이다. 근수가 얻을 수 있는 최종 에너지의 최댓값을 구해보자.

입력

첫 번째 줄에는 두 개의 정수 $ N $과 $ K $가 주어진다. $( 1 \leq N \leq 50, 0 \leq K \leq 1\,000 )$

그 다음 $ N $개의 줄에는 각각 $ N $개의 정수 $ A_{ij} $가 주어진다. $( -10 \leq A_{ij} \leq 10 )$

그 다음 $ N $개의 줄에는 각각 $ N $개의 정수 $ B_{ij} $가 주어진다. $( 0 \leq B_{ij} \leq 1\,000 )$

출력

최종 에너지의 최댓값을 출력한다.

예제 입력 1

2 10
2 0
1 -1
1 40
40 40

예제 출력 1

117

맨 위에 있는 격자판 $2$개의 전압 $2, 0$을 각각 $-1, 1$로 바꾼다.

전압을 바꾸는데 에너지가 총 $43$만큼 소모되었고, 그 후 격자판들의 상호작용으로 인하여 총 $160$만큼의 에너지가 올라가서 근수는 최종적으로 $117$의 에너지를 가지게 된다.

예제 입력 2

2 10
2 0
1 1
1000 1000
1000 1000

예제 출력 2

-80

출처

University > 서강대학교 > Sogang Programming Contest > 2024 Sogang Programming Contest > Champion I번