I tried a lot of test cases, and I haven’t been able to locate any case where the program is giving a wrong answer. Can someone locate the fault? Here’s my code:
Edit: I made a few changes and the program is now working. I took the global variables in main() and removed the additional array cache[][]. But I would like to know, why was it giving an error in the earlier code, as its the same code!
Corrected code: http://www.codechef.com/viewsolution/2029342
#include <stdio.h>
#include <stdlib.h>
int rows, z[100][100],cache[100][100];
int main()
{
int t,k,i,j;
scanf("%d",&t);
while(t--)
{
memset(cache, -1, sizeof(cache[0][0]) * 100 * 100);
scanf("%d",&rows);
for(k = 1,i = 0; i < rows; i++)
{
for(j = 0 ; j < k;j++)
{
scanf("%d",&z[i][j]);
}
k++;
}
for(i = rows - 2;i >= 0;i--)
{
for(j = 0;j <= i;j++)
{
if(i == (rows - 2))
cache[i][j] = z[i][j] + ((z[i+1][j] > z[i+1][j+1]) ? z[i+1][j] : z[i+1][j+1]);
else
cache[i][j] = z[i][j] + ((cache[i+1][j] > cache[i+1][j+1]) ? cache[i+1][j] : cache[i+1][j+1]);
}
}
printf("%d\n",cache[0][0]);
}
return 0;
}
…