시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 249 52 46 31.081%

문제

상근이는 이상하게 정사각행렬을 아름답다고 생각한다. 상근이는 행렬이 얼마나 아름다운지를 숫자로 나타낸다.

A를 행렬의 주 대각선 성분의 합이라고 하자. 또, B는 또다른 대각선 성분의 합이라고 하자. 이 때, 행렬의 아름다운 정도는 A-B가 된다.

N×N크기의 행렬이 주어졌을 때, 아름다운 정도가 가장 큰 부분 행렬을 구하는 프로그램을 작성하시오.

주 대각선은 행렬의 가장 왼쪽 위에서 시작하는 대각선이다.

입력

첫째 줄에 행렬의 크기 N이 주어진다. (2 ≤ N ≤ 400) 다음 N개의 줄에는 행렬의 성분이 공백으로 구분되어 주어진다. 각 성분은 [-1000,1000] 범위 안에 들어있다.

출력

첫째 줄에 입력으로 주어진 행렬의 부분 행렬 중 아름다운 정도가 가장 큰 것의 아름다운 정도를 출력한다.

예제 입력 1

2 
1 -2
4 5

예제 출력 1

4

힌트

W3sicHJvYmxlbV9pZCI6IjI4MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVkNTg5XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0XHVjMGMxXHVkNTU4XHVhYzhjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWM1NDRcdWI5ODRcdWIyZjVcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTg5XHViODJjXHVjNzc0IFx1YzViY1x1YjljOFx1YjA5OCBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjRcdWM5YzBcdWI5N2MgXHVjMjJiXHVjNzkwXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+QVx1Yjk3YyBcdWQ1ODlcdWI4MmNcdWM3NTggXHVjOGZjIFx1YjMwMFx1YWMwMVx1YzEyMCBcdWMxMzFcdWJkODRcdWM3NTggXHVkNTY5XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHViNjEwLCBCXHViMjk0IFx1YjYxMFx1YjJlNFx1Yjk3OCBcdWIzMDBcdWFjMDFcdWMxMjAgXHVjMTMxXHViZDg0XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NCBcdWI1NGMsIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVjODE1XHViM2M0XHViMjk0IEEtQlx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk4mdGltZXM7Tlx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YzgxNVx1YjNjNFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YmQ4MFx1YmQ4NCBcdWQ1ODlcdWI4MmNcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzhmYyBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3NDAgXHVkNTg5XHViODJjXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDQwMCkgXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWMxMzFcdWJkODRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMxMzFcdWJkODRcdWM3NDAgWy0xMDAwLDEwMDBdIFx1YmM5NFx1YzcwNCBcdWM1NDhcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWQ1ODlcdWI4MmNcdWM3NTggXHViZDgwXHViZDg0IFx1ZDU4OVx1YjgyYyBcdWM5MTEmbmJzcDtcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVjODE1XHViM2M0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzgzXHVjNzU4IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWM4MTVcdWIzYzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNQVRSSVgiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIHdlIGFsbCBrbm93LCB3ZSBsaXZlIGluc2lkZSB0aGUgbWF0cml4IHRoYXQgaXMgZGl2aWRlZCBpbnRvIE4gcm93cyBhbmQgTiBjb2x1bW5zLiBBbiBpbnRlZ2VyIGlzIHdyaXR0ZW4gaW50byBlYWNoIG9uZSBvZiB0aGUgTnhOIGNlbGxzIG9mIHRoZSBtYXRyaXguIEluIG9yZGVyIHRvIGxlYXZlIHRoZSBtYXRyaXgsIHdlIG11c3QgZmluZCB0aGUgbW9zdCBiZWF1dGlmdWwgc3F1YXJlIChzcXVhcmUtc2hhcGVkIHN1Yi1tYXRyaXgpIGNvbnRhaW5lZCBpbiB0aGUgbWF0cml4LiZuYnNwOzxcL3A+XHJcblxyXG48cD5JZiB3ZSBkZW5vdGUgYnkgQSB0aGUgc3VtIG9mIGFsbCBpbnRlZ2VycyBvbiB0aGUgbWFpbiBkaWFnb25hbCBvZiBzb21lIHNxdWFyZSwgYW5kIGJ5IEIgdGhlIHN1bSBvZiB0aGUgb3RoZXIgZGlhZ29uYWwsIHRoZW4gdGhlIGJlYXV0eSBvZiB0aGF0IHNxdWFyZSBpcyBBIC0gQi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhlIG1haW4gZGlhZ29uYWwgb2YgYSBzcXVhcmUgaXMgdGhlIGRpYWdvbmFsIHRoYXQgcnVucyBmcm9tIHRoZSB0b3AgbGVmdCBjb3JuZXIgdG8gdGhlIGJvdHRvbSByaWdodCBjb3JuZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDQwMCksIHRoZSBzaXplIG9mIHRoZSBtYXRyaXguJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTiBsaW5lcyBlYWNoIGNvbnRhaW4gTiBpbnRlZ2VycyBpbiB0aGUgcmFuZ2UgWy0xMDAwLCAxMDAwXSwgdGhlIGVsZW1lbnRzIG9mIHRoZSBtYXRyaXguPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtYXhpbXVtIGJlYXV0eSBvZiBhIHNxdWFyZSBmb3VuZCBpbiB0aGUgbWF0cml4LiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #1 2번

  • 잘못된 번역을 찾은 사람: august14
  • 문제를 번역한 사람: baekjoon