시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB236689853232.598%

문제

A나라와 B나라가 국경선을 놓고 몇 년째 싸우고 있다. 분쟁 지역의 크기는 직사각형이고, R×C 개의 칸으로 나누어져 있다. 모든 칸에는 사과 나무 또는 바나나 나무가 심어져 있다.

방금, 기나긴 영토 분쟁을 끝내기 위해 중립국에서 협상가 김상근이 도착했다. 상근이는 불도저를 이용해 일부 칸에 있는 나무를 모두 제거하고, 그러한 칸을 국경선으로 이용하려고 한다. 불도저는 가장 왼쪽 윗칸에서 출발하며, 한 칸 아래, 오른쪽, 오른쪽 아래 대각선으로 이동할 수 있다. 불도저는 오른쪽 아랫칸에 도착할 때까지 이동한다.

A는 불도저가 지나간 길의 아래쪽을 가지게 되고, B는 위쪽을 가지게 된다. 따라서, 땅을 하나도 받지 못하는 경우가 생길 수도 있다.

김상근은 A에 사는 사람들은 사과를 좋아하고, B에 사는 사람들은 바나나를 좋아한다는 사실을 알고 있다. 따라서, 불도저가 지나간 길의 아래쪽에 있는 사과 나무의 개수와 위쪽에 있는 바나나 나무 개수의 합을 크게 만들려고 한다.

가능한 합 중 가장 큰 합을 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 땅의 크기 R과 C가 주어진다. (2 ≤ R,C ≤ 1500)

다음 R개 줄에는 각 칸에 심어져있는 나무와 개수가 주어진다. 사과는 A, 바나나는 B이고, 각 칸에 심어져 있는 나무의 개수는 1보다 크거나 같고, 99보다 작거나 같다.

출력

가능한 합 중 가장 큰 것을 출력한다. 

예제 입력 1

4 3
B2 B3 B5
A3 B1 A1
A2 A4 B1
B1 B3 A3

예제 출력 1

17

예제 입력 2

3 5
A5 A2 B3 A6 B2
A1 B20 A5 B3 B6
A3 A5 B3 B8 A3

예제 출력 2

37

힌트

첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다.

W3sicHJvYmxlbV9pZCI6IjMxMTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWFjZmNcdWM2NDAgXHViYzE0XHViMDk4XHViMDk4IiwiZGVzY3JpcHRpb24iOiI8cD5BXHViMDk4XHViNzdjXHVjNjQwIEJcdWIwOThcdWI3N2NcdWFjMDAgXHVhZDZkXHVhY2JkXHVjMTIwXHVjNzQ0IFx1YjE5M1x1YWNlMCBcdWJhODcgXHViMTQ0XHVjOWY4IFx1YzJmOFx1YzZiMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmQ4NFx1YzdjMSBcdWM5YzBcdWM1ZWRcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NFx1YWNlMCwgUiZ0aW1lcztDIFx1YWMxY1x1Yzc1OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWMwYWNcdWFjZmMgXHViMDk4XHViYjM0IFx1YjYxMFx1YjI5NCBcdWJjMTRcdWIwOThcdWIwOTggXHViMDk4XHViYjM0XHVhYzAwIFx1YzJlY1x1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMyOVx1YWUwOCwgXHVhZTMwXHViMDk4XHVhZTM0IFx1YzYwMVx1ZDFhMCBcdWJkODRcdWM3YzFcdWM3NDQgXHViMDVkXHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM5MTFcdWI5YmRcdWFkNmRcdWM1ZDBcdWMxMWMgXHVkNjExXHVjMGMxXHVhYzAwIFx1YWU0MFx1YzBjMVx1YWRmY1x1Yzc3NCBcdWIzYzRcdWNjMjlcdWQ1ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJkODhcdWIzYzRcdWM4MDBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0IFx1Yzc3Y1x1YmQ4MCBcdWNlNzhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjODFjXHVhYzcwXHVkNTU4XHVhY2UwLCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVjZTc4XHVjNzQ0IFx1YWQ2ZFx1YWNiZFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJkODhcdWIzYzRcdWM4MDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MTdcdWNlNzhcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHViYTcwLCBcdWQ1NWMgXHVjZTc4IFx1YzU0NFx1Yjc5OCwgXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1YjMwMFx1YWMwMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViZDg4XHViM2M0XHVjODAwXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3YWJcdWNlNzhcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTYwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFcdWIyOTQgXHViZDg4XHViM2M0XHVjODAwXHVhYzAwIFx1YzljMFx1YjA5OFx1YWMwNCBcdWFlMzhcdWM3NTggXHVjNTQ0XHViNzk4XHVjYWJkXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWM4YyBcdWI0MThcdWFjZTAsIEJcdWIyOTQgXHVjNzA0XHVjYWJkXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViNTQ1XHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YjNjNCBcdWJjMWJcdWM5YzAgXHViYWJiXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWMwZGRcdWFlMzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTQwXHVjMGMxXHVhZGZjXHVjNzQwIEFcdWM1ZDAgXHVjMGFjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWMwYWNcdWFjZmNcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHVhY2UwLCBCXHVjNWQwIFx1YzBhY1x1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDAgXHViYzE0XHViMDk4XHViMDk4XHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWJkODhcdWIzYzRcdWM4MDBcdWFjMDAgXHVjOWMwXHViMDk4XHVhYzA0IFx1YWUzOFx1Yzc1OCBcdWM1NDRcdWI3OThcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1YWNmYyBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YzcwNFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzE0XHViMDk4XHViMDk4IFx1YjA5OFx1YmIzNCBcdWFjMWNcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1ZDA2Y1x1YWM4YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTY5IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNTQ1XHVjNzU4IFx1ZDA2Y1x1YWUzMCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IFIsQyAmbGU7IDE1MDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YzJlY1x1YzViNFx1YzgzOFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM2NDAgXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMGFjXHVhY2ZjXHViMjk0IEEsIFx1YmMxNFx1YjA5OFx1YjA5OFx1YjI5NCBCXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YzJlY1x1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDk5XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU2OSBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjAgXHViZDg4XHViM2M0XHVjODAwXHVhYzAwIFx1YzYyNFx1Yjk3OFx1Y2FiZC1cdWM1NDRcdWI3OTgsIFx1YzYyNFx1Yjk3OFx1Y2FiZC1cdWM1NDRcdWI3OTgsIFx1YzU0NFx1Yjc5OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiBcdWFjYmRcdWI4NWNcdWM3NTggXHVjNTQ0XHViNzk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWFjZmMgXHViMDk4XHViYjM0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAzKzIrND05XHVhYzFjXHVjNzc0XHVhY2UwLCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmMxNFx1YjA5OFx1YjA5OCBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDMrNT04XHVhYzFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzExNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJBR0VSIiwiZGVzY3JpcHRpb24iOiI8cD5JbmhhYml0YW50cyBvZiBuZWlnaGJvdXJpbmcgdmlsbGFnZXMgKGNhbGwgdGhlIHZpbGxhZ2VzIEEgYW5kIEIpIGNhbm5vdCBzZXR0bGUgdGhlaXIgYm9yZGVyIGRpc3B1dGUuIFRoZSBkaXNwdXRlZCBhcmVhIGlzIHJlY3Rhbmd1bGFyLCBjb21wb3NlZCBvZiBSJnRpbWVzO0MgdW5pdCBjZWxscyBvZiBsYW5kLiBFdmVyeSBjZWxsIGhhcyBlaXRoZXIgc29tZSBudW1iZXIgb2YgYXBwbGUgdHJlZXMgb3Igc29tZSBudW1iZXIgb2YgYmFuYW5hIHRyZWVzIGdyb3dpbmcgaW4gaXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgZm9yZWlnbiBjb3Vuc2VsbG9yIGhhcyBiZWVuIGFza2VkIHRvIG1lZGlhdGUgaW4gb3JkZXIgdG8gc2V0dGxlIHRoZSBkaXNwdXRlLiBIZSBoYXMgZGVjaWRlZCB0aGF0IGEgYnVsbGRvemVyIHdpbGwgcGFzcyB0aHJvdWdoIHRoZSBhcmVhIGFuZCBkZXN0cm95IGFsbCB0cmVlcyBpbiB0aGUgY2VsbHMgaXQgZ29lcyB0aHJvdWdoLiBUaGUgYnVsbGRvemVyIHdpbGwgc3RhcnQgaW4gdGhlIHVwcGVyLWxlZnQgY29ybmVyIG9mIHRoZSBhcmVhIGFuZCBhbHdheXMgbW92ZSBvbmUgY2VsbCBkb3duLCByaWdodCBvciBkaWFnb25hbGx5IGRvd24tcmlnaHQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBidWxsZG96ZXIgc3RvcHMgd2hlbiBpdCByZWFjaGVzIHRoZSBsb3dlci1yaWdodCBjb3JuZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB2aWxsYWdlIEEgd2lsbCBnZXQgdGhlIGxhbmQgYmVsb3cgdGhlIGJ1bGxkb3plciYjMzk7cyBwYXRoLCB3aGlsZSB2aWxsYWdlIEIgd2lsbCBnZXQgdGhlIGxhbmQgYWJvdmUgaXQuIE5vdGUgdGhhdCBpdCBpcyBwb3NzaWJsZSBmb3Igb25lIG9mIHRoZSB2aWxsYWdlcyB0byByZWNlaXZlIG5vIGxhbmQgYXQgYWxsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY291bnNlbGxvciBub3RpY2VkIHRoYXQgcGVvcGxlIGluIHZpbGxhZ2UgQSBwcmVmZXIgYXBwbGVzLCB3aGlsZSBwZW9wbGUgaW4gdmlsbGFnZSBCIHByZWZlciBiYW5hbmFzLiBTbyBoZSBkZWNpZGVkIHRvIGNob29zZSB0aGUgYnVsbGRvemVyJiMzOTtzIHBhdGggc28gdGhhdCB0aGUgc3VtIG9mIHRoZSBudW1iZXJzIG9mIGFwcGxlIHRyZWVzIGJlbG93IGl0cyBwYXRoIGFuZCBiYW5hbmEgdHJlZXMgYWJvdmUgaXRzIHBhdGggaXMgdGhlIGxhcmdlc3QgcG9zc2libGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhpcyBsYXJnZXN0IHBvc3NpYmxlIHN1bS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VycyBSIGFuZCBDICgyICZsZTsgUiwgQyAmbGU7IDE1MDApLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgYXJlYS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIFIgbGluZXMgY29udGFpbnMgQyBkZXNjcmlwdGlvbnMgb2YgYSBjZWxsIG9mIGxhbmQuIEVhY2ggc3VjaCBkZXNjcmlwdGlvbiBjb25zaXN0cyBvZiB0aGUgbGV0dGVyICYjMzk7QSYjMzk7IChhcHBsZXMpIG9yICYjMzk7QiYjMzk7IChiYW5hbmFzKSBhbmQgdGhlIG51bWJlciBvZiBzdWNoIHRyZWVzIGluIHRoZSBjZWxsLiBFYWNoIGNlbGwgY29udGFpbnMgYmV0d2VlbiAxIGFuZCA5OSB0cmVlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGxhcmdlc3QgcG9zc2libGUgc3VtIGFzIGRlc2NyaWJlZCBhYm92ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBmaXJzdCBleGFtcGxlLCB0aGUgYnVsbGRvemVyIHNob3VsZCBtb3ZlIGRvd24tcmlnaHQsIGRvd24tcmlnaHQgYW5kIGRvd24uIFRoZXJlIHdpbGwgYmUgMysyKzQ9OSBhcHBsZSB0cmVlcyBiZWxvdyBpdHMgcGF0aCBhbmQgMys1PTggYmFuYW5hIHRyZWVzIGFib3ZlIHRoZSBwYXRoLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2009 > National Competition #2 - Juniors 2번