3 / 3
Aug 2012

it the 3th time i tried new code for DCEPC206 and still get TLE!!
https://www.spoj.pl/problems/DCEPC206/

i need some help to know which point still can be improved
my code

#include <iostream>
using namespace std;
long Tnz(int* tnz,int tt,int mat_m)
{
	long bit=0;
	for(;;) 
	{ 
		if(tnz[tt]>mat_m&&tt>-1) { tnz[tt+1]=tnz[tt]; bit+=tnz[tt]; }
		else { tnz[tt+1]=mat_m; break; }
		--tt;
	}
	return bit;
}
int main()
{
	int n,N;
	long S,sum;
	int mat[100000];
	int tnz[100001],tt;
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	{
		cin>>N;
		sum=0;
		S=0;
		tt=-1;
		for(int m=0;m<N;++m)
		{
			scanf("%d",&mat[m]);
			S+=sum-Tnz(tnz,tt,mat[m]);
			sum+=mat[m];
			++tt;
		}
		printf("%ld\n",S);
	}
	return 0;
}

Tnz : to compare input num with last nums and arrange them and sum nums that bigger ( 'bit' that returned) , to subtract from the sum ( 'sum' ) of all previus nums

thanks for help smile

  • created

    Jul '12
  • last reply

    Aug '12
  • 2

    replies

  • 134

    views

  • 2

    users

  • 1

    link

Do you understand why you get TLE? Your operational complexity is O(N^2). With N this large, that is far too slow.

So i've to change all the way that i think with this problem frowning
But i,ve new code now, i hope it will be AC
thanks very match smile