I'm stuck with this problem. My code is alwyas "time-exceeded" in test cast 31 even if I implemented DP-solution with n^2.

Could anyone tell me why my code never passes the test cases?

Below is my code.

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

using namespace std;

int matrix[1001][1001];
int count2[1001][1001];
int count5[1001][1001];
char dir2[1001][1001];
char dir5[1001][1001];

int factor_of_k(int n, int k)
{
	int count = 0;

	while (n % k == 0)
	{
		n /= k;
		count++;
	}

	return count;
}

int main()
{
	int n;

	cin >> n;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> matrix[i][j];

	for (int i = 0; i <= n; i++)
	{
		count2[i][0] = 1999999999;
		count2[0][i] = 1999999999;
		count5[i][0] = 1999999999;
		count5[0][i] = 1999999999;
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			int up = count2[i-1][j];
			int left = count2[i][j-1];

			if (i == 1 && j == 1)
				count2[i][j] = factor_of_k(matrix[i][j], 2);
			else
				count2[i][j] = min(up, left) + factor_of_k(matrix[i][j], 2);

			dir2[i][j] = (up < left ? 'D' : 'R');

			up = count5[i-1][j];
			left = count5[i][j-1];

			if (i == 1 && j == 1)
				count5[i][j] = factor_of_k(matrix[i][j], 5);
			else
				count5[i][j] = min(up, left) + factor_of_k(matrix[i][j], 5);
			
			dir5[i][j] = (up < left ? 'D' : 'R');
		}


	if (count2[n][n] < count5[n][n])
	{
		cout << count2[n][n] << endl;

		int i = n, j = n;
		vector<char> path;

		while (i != 1 || j != 1)
		{
			path.push_back(dir2[i][j]);

			if (dir2[i][j] == 'D' && i >= 2) i--;
			else j--;
		}

		for (int k = 0; k < path.size(); k++)
			cout << path[path.size() - k - 1];

		cout << endl;
	}
	else
	{
		cout << count5[n][n] << endl;

		int i = n, j = n;
		vector<char> path;

		while (i != 1 || j != 1)
		{
			path.push_back(dir5[i][j]);

			if (dir5[i][j] == 'D' && i >= 2) i--;
			else j--;
		}

		for (int k = 0; k < path.size(); k++)
			cout << path[path.size() - k - 1];

		cout << endl;
	}

	return 0;
}