#include #include #include #include #include int recursiveN2(int posX, int max, std::vector> matrix, int sum) { sum += matrix[matrix.size()-1][posX]; if(posX < max - 1) { sum = recursiveN2(posX+1,max,matrix, sum); } return sum; } int recursiveN1(int posX, int max, std::vector> matrix, int sum) { int sum1 = 0; int sum2 = 0; sum += matrix[matrix.size()-2][posX]; printf("%d\n",sum); if(posX > 0) { sum1 = recursiveN1(posX-1, max, matrix, sum); } sum2 = recursiveN2(posX,max,matrix, sum); return (sum1 > sum2) ? sum1 : sum2; } int recursiveN3(int posX, int posY, int max, std::vector> matrix, int sum) { sum += matrix[posY][posX]; if(posX == max-1 && posY == 1) { return sum; } int sum1 = -10000000; int sum2 = -10000000; if(posY == 0) { sum1 = recursiveN3(posX,posY+1,max,matrix,sum); } if(posX < max -2) { sum2 = recursiveN3(posX+1,posY,max,matrix,sum); } return (sum1 > sum2) ? sum1 : sum2; } int main() { int numOfRow, numOfCol; char buffer[1024]; std::vector> matrix; std::vector row; char* token; read(1,buffer,sizeof(buffer)); sscanf(buffer,"%d %d",&numOfRow, &numOfCol); for(int i = 0; i < numOfRow; i++) { read(1,buffer,sizeof(buffer)); for(int k = 0; k < numOfCol; k++) { if( k == 0 ) { token = strtok(buffer," "); } else if(k!= numOfCol - 1) { token = strtok(NULL," "); } else { token = strtok(NULL,"\n"); } row.push_back(atoi(token)); } matrix.push_back(row); row.erase(row.begin(),row.end()); } int posX = 0, posY = 0; int max = 0; int dir = 0; int sum = 0; for(int i = 0; i < numOfRow - 2; i++) { for(int k = 0; k < numOfCol; k++) { sum += matrix[i][k]; } } if(numOfRow == 2) { if(numOfCol % 2 == 1) sum = recursiveN1(numOfCol-1,numOfCol,matrix,sum); else { sum = recursiveN3(numOfCol-2, 0,numOfCol,matrix,sum); } }else { sum = recursiveN1(numOfCol-1,numOfCol,matrix,sum); } posX = numOfCol - 1; posY = numOfRow - 2; printf("%d\n",sum); return 0; }