Tournament(ZCO '14) Need a efficient way!

general
1

http://www.iarcs.org.in/inoi/2013/zco2013/zco2013-1a.php

getting out of time for 5 cases of total 13 cases and rest are correct.

Can anyone help me to make my approach more efficient;
here’s my code:

#include<iostream>
#include<cstdio>
using namespace std;

int main()
{ long int n,i;
   scanf("%ld",&n);
   int st[n];
   for(i=0; i<n; i++)
   scanf("%d",&st[i]);

   long long int rev=0;

   for(i=0; i<n; i++)
   { long int j=i+1;
       for( ;j<n; j++ )
        {int tst = (st[i] - st[j] );
         if (tst<0)
            tst= -(tst);
            rev= rev + tst;
        }

   }

   printf("%lld",rev);
return 0;
}
2

The problem can be solved in O(n) time using basic computations .
observe that the ith element will appear i*(n-i) time .

so simply sum like this :-

ans=0;

while( i< n )
{

ans=ans+ array[i] ** i ** (n-i);

i++;

}

it is same as the problem

thanks for accepting the solution in advance

1 Like