## Editorial for coffee run

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

for this problem; first, you need to see that the first row is computed by adding up all the values in the cells. in other words, if you want to go to a cell in the first row, you just go right starting from the $$(1, 1)$$ cell and take each cell's coffee beans. there is no other way. similarly, for the first column, you start from the (1, 1) cell, go down, and collect as you go.

after computing the first row and the first column, suppose now you want to find the maximal amount for the cell $$(i, j)$$. you can come to this cell either from the left cell or from the top cell. namely either from $$(i-1, j)$$ or $$(i, j-1)$$. so the maximum value for $$(i, j)$$ is equal to $$max((i-1, j), (i, j-1))$$ + the amount of coffee beans in $$(i, j)$$.

to sum up; first, you calculate the values for the first row and the first column. then, starting from $$(2, 2)$$, you calculate the values by looking at their left and top neighbors, whichever is greater.

here is an example code:

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
std::vector <std::vector <int>> grid;
int r, c, ar, ac, t, i, j;
std::cin >> r >> c >> ar >> ac;
for(i=0; i<r; i++){
std::vector <int> tmp;
for(j=0; j<c; j++){
std::cin >> t;
tmp.push_back(t);
}
grid.push_back(tmp);
}

int sol[r][c];

sol=grid;

for(i=1; i<r; i++){
sol[i]=sol[i-1]+grid[i];
}

for(i=1; i<c; i++){
sol[i]=sol[i-1]+grid[i];
}

for(i=1; i<r; i++){
for(j=1; j<c; j++){
sol[i][j]=std::max(sol[i-1][j], sol[i][j-1])+grid[i][j];
}
}

std::cout << sol[ar-1][ac-1] << std::endl;
return 0;
}