po4emu u menia Time Limit Exceeded? (

Edited by author 12.06.2012 08:19
#include <iostream>
using namespace std;
int main()
{
 int a[4000],a2[4000],a3[4000],i,j,l,n,n2,n3,k=0;
 cin>>n;
 for(i=1;i<=n;i++)
 cin>>a[i];
                cin>>n2;
                          for(j=1;j<=n2;j++)
                               cin>>a2[j];
cin>>n3;
for(l=1;l<=n3;l++)
cin>>a3[l];
          for(i=1;i<=n;i++)
          {
              for(j=1;j<=n2;j++)
              {
                  for(l=1;l<=n3;l++)
                  {
                      if(a[i]==a2[j] && a[i]==a3[l]) k++;
                  }
              }
          }
cout<<k;
return 0;
}


Edited by author 12.06.2012 08:25

Your algorithm has complexity O(N^3) while N = 4000. It is very long. Try to use binary search, then you will find solution with complexity O(N * logN * logN).

This problem can be solved by O(N) time... If you have a good hash function, of course
And O(N * log N) instead of yours O(N * log N * log N) using map.

Edited by author 25.03.2013 22:24