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 if my code.

include

include

include

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;

}