[伯俊]操縦2169ロボット

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 1005;

int N, M;
int value[MAXN][MAXN];
int dp[MAXN][MAXN];

void getdp() {
	//맨 첫줄
	//오른쪽에서 오는 경우 뿐
	dp[1][1] = value[1][1];
	for (int col = 2; col <= M; ++col)
		dp[1][col] = dp[1][col-1] + value[1][col];

	//두번째 줄 부터 마지막 줄 까지
	for (int row = 2; row <= N; ++row) {
		int leftdp[MAXN];
		int rightdp[MAXN];

		//바로 위에서 내려오거나 왼쪽에서 오기
		leftdp[1] = dp[row-1][1] + value[row][1];
		for (int col = 2; col <= M; ++col)
			leftdp[col] = max(dp[row-1][col], leftdp[col-1]) + value[row][col];

		//바로 위에서 내려오거나 오른쪽에서 오기
		rightdp[M] = dp[row - 1][M] + value[row][M];
		for (int col = M-1; col >= 1; --col)
			rightdp[col] = max(dp[row - 1][col], rightdp[col + 1]) + value[row][col];

		//둘 중 최댓값을 최종 dp에 저장
		for (int col = 1; col <= M; ++col)
			dp[row][col] = max(leftdp[col], rightdp[col]);
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			cin >> value[i][j];

	getdp();
	cout << dp[N][M];

	return 0;
}