Untitled

#include <iostream>
#include <vector>
#include <map>

/*
Bu adam ya 1 xana irəli, ya da 1 xana aşağı gedə bilir. 
Elə bil proram yazın ki, ən sağ və ən aşağı nöqtəyə gələrkən keçdiyi xanalardakı ədədləri toplamalıdır.
bütün ehtimallar içində ən çox toplaya biləcəyi xalı tapın
*/

using namespace std;

vector<vector<int>> inp = {
	{3, -2, 2, 6, 1},
	{4, 1, 7, 5, -3},
	{1, 6, 3, 4, 2},
	{4, 3, 8, 4, 8},
	{7, 9, 6, -1, 3}
};

map<vector<int>, int> memo;

int greatestScore(int x, int y, int size) {
	if (memo[{x, y}]) return memo[{x, y}];
	int right = inp[x][y];
	int down = inp[x][y];

	if (x < size - 1) {
		int temp = greatestScore(x + 1, y, size);
		memo[{x + 1, y}] = temp;
		down += temp;
	}
	if (y < size - 1) {
		int temp = greatestScore(x, y + 1, size);
		memo[{x, y + 1}] = temp;
		right += temp;
	}

	return (right > down) ? right : down;
}

int main() {
	std::cout << greatestScore(0, 0, (int)inp.size()) << std::endl;

	return 0;
}