시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 849 312 170 32.136%

문제

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

힌트

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

W3sicHJvYmxlbV9pZCI6IjMxMTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWFjZmNcdWM2NDAgXHViYzE0XHViMDk4XHViMDk4IiwiZGVzY3JpcHRpb24iOiI8cD5BXHViMDk4XHViNzdjXHVjNjQwIEJcdWIwOThcdWI3N2NcdWFjMDAgXHVhZDZkXHVhY2JkXHVjMTIwXHVjNzQ0IFx1YjE5M1x1YWNlMCBcdWJhODcgXHViMTQ0XHVjOWY4IFx1YzJmOFx1YzZiMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmQ4NFx1YzdjMSBcdWM5YzBcdWM1ZWRcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NFx1YWNlMCwgUiZ0aW1lcztDIFx1YWMxY1x1Yzc1OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWMwYWNcdWFjZmMgXHViMDk4XHViYjM0IFx1YjYxMFx1YjI5NCBcdWJjMTRcdWIwOThcdWIwOTggXHViMDk4XHViYjM0XHVhYzAwIFx1YzJlY1x1YzViNFx1YzgzOCBcdWM3ODdcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMyOVx1YWUwOCwgXHVhZTMwXHViMDk4XHVhZTM0IFx1YzYwMVx1ZDFhMCBcdWJkODRcdWM3YzFcdWM3NDQgXHViMDVkXHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM5MTFcdWI5YmRcdWFkNmRcdWM1ZDBcdWMxMWMgXHVkNjExXHVjMGMxXHVhYzAwIFx1YWU0MFx1YzBjMVx1YWRmY1x1Yzc3NCBcdWIzYzRcdWNjMjlcdWQ1ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJkODhcdWIzYzRcdWM4MDBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0IFx1Yzc3Y1x1YmQ4MCBcdWNlNzhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjODFjXHVhYzcwXHVkNTU4XHVhY2UwLCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVjZTc4XHVjNzQ0IFx1YWQ2ZFx1YWNiZFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJkODhcdWIzYzRcdWM4MDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MTdcdWNlNzhcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHViYTcwLCBcdWQ1NWMgXHVjZTc4IFx1YzU0NFx1Yjc5OCwgXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1YjMwMFx1YWMwMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViZDg4XHViM2M0XHVjODAwXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3YWJcdWNlNzhcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTYwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFcdWIyOTQgXHViZDg4XHViM2M0XHVjODAwXHVhYzAwIFx1YzljMFx1YjA5OFx1YWMwNCBcdWFlMzhcdWM3NTggXHVjNTQ0XHViNzk4XHVjYWJkIFx1YWMwMFx1YzljMFx1YWM4YyBcdWI0MThcdWFjZTAsIEJcdWIyOTQgXHVjNzA0XHVjYWJkIFx1YWMwMFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViNTQ1XHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YjNjNCBcdWJjMWJcdWM5YzAgXHViYWJiXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWMwZGRcdWFlMzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTQwXHVjMGMxXHVhZGZjXHVjNzQwIEFcdWM1ZDAgXHVjMGFjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWMwYWNcdWFjZmNcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHVhY2UwLCBCXHVjNWQwIFx1YzBhY1x1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDAgXHViYzE0XHViMDk4XHViMDk4XHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWJkODhcdWIzYzRcdWM4MDBcdWFjMDAgXHVjOWMwXHViMDk4XHVhYzA0IFx1YWUzOFx1Yzc1OCBcdWM1NDRcdWI3OThcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1YWNmYyBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YzcwNFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzE0XHViMDk4XHViMDk4IFx1YjA5OFx1YmIzNCBcdWFjMWNcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1ZDA2Y1x1YWM4YyBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTY5IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNTQ1XHVjNzU4IFx1ZDA2Y1x1YWUzMCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IFIsQyAmbGU7IDE1MDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YzJlY1x1YzViNFx1YzgzOFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM2NDAgXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMGFjXHVhY2ZjXHViMjk0IEEsIFx1YmMxNFx1YjA5OFx1YjA5OFx1YjI5NCBCXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YzJlY1x1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDk5XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU2OSBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWJkODhcdWIzYzRcdWM4MDBcdWFjMDAgXHVjNjI0XHViOTc4XHVjYWJkLVx1YzU0NFx1Yjc5OCwgXHVjNjI0XHViOTc4XHVjYWJkLVx1YzU0NFx1Yjc5OCwgXHVjNTQ0XHViNzk4XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1YWNmYyBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDMrMis0PTlcdWFjMWNcdWM3NzRcdWFjZTAsIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzE0XHViMDk4XHViMDk4IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMys1PThcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTE0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQkFHRVIiLCJkZXNjcmlwdGlvbiI6IjxwPkluaGFiaXRhbnRzIG9mIG5laWdoYm91cmluZyB2aWxsYWdlcyAoY2FsbCB0aGUgdmlsbGFnZXMgQSBhbmQgQikgY2Fubm90IHNldHRsZSB0aGVpciBib3JkZXIgZGlzcHV0ZS4gVGhlIGRpc3B1dGVkIGFyZWEgaXMgcmVjdGFuZ3VsYXIsIGNvbXBvc2VkIG9mIFImdGltZXM7QyB1bml0IGNlbGxzIG9mIGxhbmQuIEV2ZXJ5IGNlbGwgaGFzIGVpdGhlciBzb21lIG51bWJlciBvZiBhcHBsZSB0cmVlcyBvciBzb21lIG51bWJlciBvZiBiYW5hbmEgdHJlZXMgZ3Jvd2luZyBpbiBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBmb3JlaWduIGNvdW5zZWxsb3IgaGFzIGJlZW4gYXNrZWQgdG8gbWVkaWF0ZSBpbiBvcmRlciB0byBzZXR0bGUgdGhlIGRpc3B1dGUuIEhlIGhhcyBkZWNpZGVkIHRoYXQgYSBidWxsZG96ZXIgd2lsbCBwYXNzIHRocm91Z2ggdGhlIGFyZWEgYW5kIGRlc3Ryb3kgYWxsIHRyZWVzIGluIHRoZSBjZWxscyBpdCBnb2VzIHRocm91Z2guIFRoZSBidWxsZG96ZXIgd2lsbCBzdGFydCBpbiB0aGUgdXBwZXItbGVmdCBjb3JuZXIgb2YgdGhlIGFyZWEgYW5kIGFsd2F5cyBtb3ZlIG9uZSBjZWxsIGRvd24sIHJpZ2h0IG9yIGRpYWdvbmFsbHkgZG93bi1yaWdodC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGJ1bGxkb3plciBzdG9wcyB3aGVuIGl0IHJlYWNoZXMgdGhlIGxvd2VyLXJpZ2h0IGNvcm5lci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHZpbGxhZ2UgQSB3aWxsIGdldCB0aGUgbGFuZCBiZWxvdyB0aGUgYnVsbGRvemVyJiMzOTtzIHBhdGgsIHdoaWxlIHZpbGxhZ2UgQiB3aWxsIGdldCB0aGUgbGFuZCBhYm92ZSBpdC4gTm90ZSB0aGF0IGl0IGlzIHBvc3NpYmxlIGZvciBvbmUgb2YgdGhlIHZpbGxhZ2VzIHRvIHJlY2VpdmUgbm8gbGFuZCBhdCBhbGwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjb3Vuc2VsbG9yIG5vdGljZWQgdGhhdCBwZW9wbGUgaW4gdmlsbGFnZSBBIHByZWZlciBhcHBsZXMsIHdoaWxlIHBlb3BsZSBpbiB2aWxsYWdlIEIgcHJlZmVyIGJhbmFuYXMuIFNvIGhlIGRlY2lkZWQgdG8gY2hvb3NlIHRoZSBidWxsZG96ZXImIzM5O3MgcGF0aCBzbyB0aGF0IHRoZSBzdW0gb2YgdGhlIG51bWJlcnMgb2YgYXBwbGUgdHJlZXMgYmVsb3cgaXRzIHBhdGggYW5kIGJhbmFuYSB0cmVlcyBhYm92ZSBpdHMgcGF0aCBpcyB0aGUgbGFyZ2VzdCBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGlzIGxhcmdlc3QgcG9zc2libGUgc3VtLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXJzIFIgYW5kIEMgKDIgJmxlOyBSLCBDICZsZTsgMTUwMCksIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBhcmVhLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgUiBsaW5lcyBjb250YWlucyBDIGRlc2NyaXB0aW9ucyBvZiBhIGNlbGwgb2YgbGFuZC4gRWFjaCBzdWNoIGRlc2NyaXB0aW9uIGNvbnNpc3RzIG9mIHRoZSBsZXR0ZXIgJiMzOTtBJiMzOTsgKGFwcGxlcykgb3IgJiMzOTtCJiMzOTsgKGJhbmFuYXMpIGFuZCB0aGUgbnVtYmVyIG9mIHN1Y2ggdHJlZXMgaW4gdGhlIGNlbGwuIEVhY2ggY2VsbCBjb250YWlucyBiZXR3ZWVuIDEgYW5kIDk5IHRyZWVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBzdW0gYXMgZGVzY3JpYmVkIGFib3ZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGZpcnN0IGV4YW1wbGUsIHRoZSBidWxsZG96ZXIgc2hvdWxkIG1vdmUgZG93bi1yaWdodCwgZG93bi1yaWdodCBhbmQgZG93bi4gVGhlcmUgd2lsbCBiZSAzKzIrND05IGFwcGxlIHRyZWVzIGJlbG93IGl0cyBwYXRoIGFuZCAzKzU9OCBiYW5hbmEgdHJlZXMgYWJvdmUgdGhlIHBhdGguJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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