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 ifs 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;↵
}↵
↵
~~~~~
↵
Could anyone tell me why my code never passes the test cases?↵
↵
Below i
↵
~~~~~↵
#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;↵
}↵
↵
~~~~~
