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 <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;
}