SUMof4 tle

[lucckygeek]

i am getting tle in https://www.spoj.pl/problems/SUMFOUR/

please help

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	int a[n][4];
	vector<int> ab;
	vector<int> cd;
	int count1=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&a[i][3]);
	}
	for(int i=0;i<n;i++)
	{
		int a1=a[i][0];
		int c=a[i][2];
		for(int j=0;j<n;j++)
		{
			int b=a[j][1];
			int d=a[j][3];
			ab.push_back(a1+b);
			cd.push_back(c+d);
		}
	}
	sort(ab.begin(),ab.end());
	//cout<<ab.size();
	long long int size=n*n;
	for(int i=0;i<size;i++)
	{
		int find=cd[i];
		find=-1*find;
		if (binary_search (ab.begin(), ab.end(), find))
		{
				int mycount = (int) count (ab.begin(), ab.end(), find);
		   		count1=count1+mycount;
		}
	}
	cout<<count1<<endl;
	return 0;
}

[leppyr64]

Of course you are getting TLE I don't know the complexity of count but I suspect it would be O(elements in array), making your complexity O(n^4).

[lucckygeek]

i tried to make complexity O(n) but still getting tle...

[leppyr64]

for(int k=0;k<size;k++)
               {
                  if(ab[k]==find)
                  {
                     cou++;
                  }
                  if(ab[k]>find)
                  {
                     break;
                  }
               }

This is no better. The complexity is exactly the same. It's O(number of elements in ab). There will be n^2 elements in ab and you have two loops of n, making yor complexity o(n^4)

[lucckygeek]

any hint....

[leppyr64]

Why not use your binary search?

You're going to need to switch to a fixed array as opposed to a vector. Memory allocation is expensive.