Ruudukko

input/code.cpp: In function 'int main()':
input/code.cpp:148:20: warning: format '%llu' expects argument of type 'long long unsigned int', but argument 2 has type 'uint64_t' {aka 'long unsigned int'} [-Wformat=]
  148 |         printf("%llu", nPath);
      |                 ~~~^   ~~~~~
      |                    |   |
      |                    |   uint64_t {aka long unsigned int}
      |                    long long unsigned int
      |                 %lu
input/code.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         scanf("%i", &d);
      |         ~~~~~^~~~~~~~~~
input/code.cpp:135:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |                         scanf("%i", &grid[i * d + j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <unordered_map>
#include <optional>

int d = 0;
std::vector<int> grid;
std::unordered_map<int, uint64_t> cache;

std::optional<uint64_t> getValueAtCache(int loc)
{
	auto found = cache.find(loc);

	if (found != cache.end())
	{
		return std::optional<uint64_t>{found->second};
	}

	else
	{
		return std::nullopt;
	}
}

uint64_t findNumPath(int x, int y)
{

	auto currNum = grid[y * d + x];
	uint64_t nPath = 0;

	for (int i = 1; i < d; i++)
	{
		//test left and right, up and down

		if ((y - i >= 0) && (y - i < d))
		{
			int g = (y - i) * d + x;
			auto gn = grid[g];
			if (gn < currNum)
			{
				nPath++;
				auto v = getValueAtCache(g);
				if (v.has_value())
				{
					nPath += v.value();
				}
				else
				{
					auto a = findNumPath(x, y - i);
					cache[g] = a;
					nPath += a;
				}
			}

		}
		if ((y + i >= 0) && (y + i < d))
		{
			int g = (y + i) * d + x;
			auto gn = grid[g];
			if (gn < currNum)
			{
				nPath++;
				auto v = getValueAtCache(g);
				if (v.has_value())
				{
					nPath += v.value();
				}
				else
				{
					auto a = findNumPath(x, y + i);
					cache[g] = a;
					nPath += a;
				}
			}
			
		}
		if ((x - i >= 0) && (x - i < d))
		{
			int g = y * d + (x - i);
			auto gn = grid[g];
			if (gn < currNum)
			{
				nPath++;
				auto v = getValueAtCache(g);
				if (v.has_value())
				{
					nPath += v.value();
				}
				else
				{
					auto a = findNumPath(x-i, y);
					cache[g] = a;
					nPath += a;
				}
			}
		}
		if ((x + i >= 0) && (x + i < d))
		{
			int g = y * d + (x + i);
			auto gn = grid[g];
			if (gn < currNum)
			{
				nPath++;
				auto v = getValueAtCache(g);
				if (v.has_value())
				{
					nPath += v.value();
				}
				else
				{
					auto a = findNumPath(x + i, y);
					cache[g] = a;
					nPath += a;
				}
			}
		}

	}
	return nPath;

}


int main()
{
	scanf("%i", &d);
	grid.resize(d * d);
	cache.reserve(d * d);
	for (int i = 0; i < d; i++)
	{
		for (int j = 0; j < d; j++)
		{
			//x is row j is column
			scanf("%i", &grid[i * d + j]);
		}
	}

	uint64_t nPath = 0;
	for (int i = 0; i < d; i++)
	{
		for (int j = 0; j < d; j++)
		{

			nPath += (findNumPath(i, j)+1) % 1000000007;
		}
	}
	printf("%llu", nPath);


}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: WRONG ANSWER

Test 6

Group: 2, 3

Verdict: WRONG ANSWER

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED