시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 260 58 52 32.704%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

2 
1 -2
4 5

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI4MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVkNTg5XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0XHVjMGMxXHVkNTU4XHVhYzhjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWM1NDRcdWI5ODRcdWIyZjVcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTg5XHViODJjXHVjNzc0IFx1YzViY1x1YjljOFx1YjA5OCBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjRcdWM5YzBcdWI5N2MgXHVjMjJiXHVjNzkwXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+QVx1Yjk3YyBcdWQ1ODlcdWI4MmNcdWM3NTggXHVjOGZjIFx1YjMwMFx1YWMwMVx1YzEyMCBcdWMxMzFcdWJkODRcdWM3NTggXHVkNTY5XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHViNjEwLCBCXHViMjk0IFx1YjYxMFx1YjJlNFx1Yjk3OCBcdWIzMDBcdWFjMDFcdWMxMjAgXHVjMTMxXHViZDg0XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NFx1YjU0YywgXHVkNTg5XHViODJjXHVjNzU4IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWM4MTVcdWIzYzRcdWIyOTQgQS1CXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+TiZ0aW1lcztOXHVkMDZjXHVhZTMwXHVjNzU4IFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVjODE1XHViM2M0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHViZDgwXHViZDg0IFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjIFx1YjMwMFx1YWMwMVx1YzEyMFx1Yzc0MCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YjMwMFx1YWMwMVx1YzEyMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTg5XHViODJjXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgNDAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTg5XHViODJjXHVjNzU4IFx1YzEzMVx1YmQ4NFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzEzMVx1YmQ4NFx1Yzc0MCBbLTEwMDAsMTAwMF0gXHViYzk0XHVjNzA0IFx1YzU0OFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWJkODBcdWJkODQgXHVkNTg5XHViODJjIFx1YzkxMSZuYnNwO1x1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWM4MTVcdWIzYzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjODNcdWM3NTggXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YzgxNVx1YjNjNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1BVFJJWCIsImRlc2NyaXB0aW9uIjoiPHA+QXMgd2UgYWxsIGtub3csIHdlIGxpdmUgaW5zaWRlIHRoZSBtYXRyaXggdGhhdCBpcyBkaXZpZGVkIGludG8gTiByb3dzIGFuZCBOIGNvbHVtbnMuIEFuIGludGVnZXIgaXMgd3JpdHRlbiBpbnRvIGVhY2ggb25lIG9mIHRoZSBOeE4gY2VsbHMgb2YgdGhlIG1hdHJpeC4gSW4gb3JkZXIgdG8gbGVhdmUgdGhlIG1hdHJpeCwgd2UgbXVzdCBmaW5kIHRoZSBtb3N0IGJlYXV0aWZ1bCBzcXVhcmUgKHNxdWFyZS1zaGFwZWQgc3ViLW1hdHJpeCkgY29udGFpbmVkIGluIHRoZSBtYXRyaXguJm5ic3A7PFwvcD5cclxuXHJcbjxwPklmIHdlIGRlbm90ZSBieSBBIHRoZSBzdW0gb2YgYWxsIGludGVnZXJzIG9uIHRoZSBtYWluIGRpYWdvbmFsIG9mIHNvbWUgc3F1YXJlLCBhbmQgYnkgQiB0aGUgc3VtIG9mIHRoZSBvdGhlciBkaWFnb25hbCwgdGhlbiB0aGUgYmVhdXR5IG9mIHRoYXQgc3F1YXJlIGlzIEEgLSBCLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgbWFpbiBkaWFnb25hbCBvZiBhIHNxdWFyZSBpcyB0aGUgZGlhZ29uYWwgdGhhdCBydW5zIGZyb20gdGhlIHRvcCBsZWZ0IGNvcm5lciB0byB0aGUgYm90dG9tIHJpZ2h0IGNvcm5lci4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgNDAwKSwgdGhlIHNpemUgb2YgdGhlIG1hdHJpeC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBOIGxpbmVzIGVhY2ggY29udGFpbiBOIGludGVnZXJzIGluIHRoZSByYW5nZSBbLTEwMDAsIDEwMDBdLCB0aGUgZWxlbWVudHMgb2YgdGhlIG1hdHJpeC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1heGltdW0gYmVhdXR5IG9mIGEgc3F1YXJlIGZvdW5kIGluIHRoZSBtYXRyaXguJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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