How to increase efficiency of matrix operation in C?

I have a N*N upper triangular matrix with property such that, all its diagonal elements are a1,a2,a3,...,aN. I want that a[i][j] (for all j>i) should be

(a[i][j-1] + a[i+1][j]) / 2.

I have many test cases, and I have to apply this property every time to calculate the answer. What is the most optimal way to do this, so that for all test cases the overall running time is less? Test cases: Inputs are N and a1,a2,...,aN.

To calculate the answer, I need to do:

a[0][0] + a[0][2] + ... + a[0][n-1] + a[2][n-1] + a[4][n-1] + ... + a[n-1][n-1].

My solution (which keeps getting timed out):

#include
double a[2000][2000];
int main(){
int test;
scanf("%d",&test);
//int arr[2000];
while(test--){
    int n,i,j;
    //scanf("%d",&n);
    scanf("%d",&n);
    for(i=0;i<n;i++){
         int num;
         scanf("%d",&num);
         if(n!=1)
            a[i][i] = num*0.5;
         else
            a[i][i] = num;
     }
    for(j=1;j<n;j++){
         int k=j;
         for(i=0;i<n-j;i++,k++){
             if(i==0 && k==n-1)
                 a[i][k] = (a[i+1][k]+a[i][k-1]);
             else
                 a[i][k] = (a[i+1][k]+a[i][k-1])*0.5;
         }
     }
     float sum=0.0;
     for(i=0;i<n;i+=2){
         if( i != n-1 )
         sum+=a[0][i]+a[n-1-i][n-1];
         else
         sum+=a[0][i];
     }
    printf("%.3f\n",sum);
}
getch();
}

Please provide some hints how to optimize the above code.

I suggest dropping the floating point and doing it fixed point. To do this I
would make a[][] of type int or short (depending upon the input
constraints) and instead of storing values x and x * 0.5, store 2x and x
respectively. At the end of the summation you can then divide by 2 to get the
true result.

The only issue this raises is that of integer overflow. You don't state any
numerical constraints but the fixed size arrays (2000x2000) suggest overflow
will not occur with long long. Alternatively the summation itself could be
floating point while the array values remain integers. I notice that your
current summation uses float which might well be slower than double.

Another minor point where you can improve the speed is in the input loop. You
have the conditional

if(n!=1)
    a[i][i] = num*0.5;
else
    a[i][i] = num;

As the loop variable i goes from 0 to n, if n is 1 then the loop only
fills a[0][0] and so this conditional can be removed from the loop. But if n
is small this will make little difference.

StackExchange Code Review Q#16265, answer score: 6