SUMTRAIN: Getting wa

general
,
1

admin please help with my code.I’ve also implemented recursion with memoization but it says Wrong Answer.I’ve run the code using DEV C++ compiler and it works fine on my system.

#include<stdio.h>
#include<stdlib.h>
#define size 4950
inline int next_int() {
 int n = 0;
 char c = getchar();
 while (!('0' <= c && c <= '9')) {
  c = getchar();
 }
 while ('0' <= c && c <= '9') {
  n = n * 10 + c - '0';
  c = getchar();
 }
 return n;
}

int a[size];

int elem(int i,int j)
{return (i-1)*i/2+j;
 }
int summ(int i,int j,int *mem)
{int sum_left=0,sum_up=0,x;
 if(j==0)
 {if(i==1)
  return a[elem(i,j)];
  else
  {sum_up=summ(i-1,j,mem)+a[elem(i,j)];
   mem[elem(i,j)]=sum_up;
   return sum_up;}
   }
 else if((x=mem[elem(i,j)])!=0)
 return x;
 else if(j==i-1)
{sum_left=summ(i-1,j-1,mem)+a[elem(i,j)];
 mem[elem(i,j)]=sum_left;
 return sum_left;}
 else
{sum_left=summ(i-1,j-1,mem)+a[elem(i,j)];
 sum_up=summ(i-1,j,mem)+a[elem(i,j)];
 if(sum_left>=sum_up)
{mem[elem(i,j)]=sum_left;
 return sum_left;}
 else 
{mem[elem(i,j)]=sum_up;
 return sum_up;}}
}
int main()
{int t,i,n,r,c,*mem;
 t=next_int();//scanf("%d",&t);//No of test cases
for(i=1;i<=t;i++)
{n=next_int();//scanf("%d",&n);//no of rows
 mem=(int *)malloc(n*(n+1)*sizeof(int)/2);
 for(r=1;r<=n;r++)//memoization array
 {for(c=0;c<r;c++)
  mem[elem(r,c)]=0;
  }
 
 for(r=1;r<=n;r++)
 {for(c=0;c<r;c++)
  a[elem(r,c)]=next_int();//scanf("%d",&a[elem(r,c)]);
  }
 int max=0,temp;
 for(c=0;c<n;c++)
 {temp=summ(n,c,mem);
  if(temp>=max)
   max=temp;
  }
printf("%d",max);
free(mem);}
return 0;

}

problem: SUMTRAIN

submission

2

Your code for example input from statement prints

59

:wink: