vendredi 5 juin 2015

SPOJ SUMFOUR.....Optimization Required .....Getting TLE after repeated optimizations

I am trying to solve SPOJ Problem SUMFOUR....I am geting TLE on test case 9 http://ift.tt/1EMAfoh

I've used the c++ algorithm library functions sort,find,count....I assume they are highly efficient functions and I don't have to edit that portion....

So,Which part of my code has to be edited and how?Here N<=4000

#include <iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<vector>

using namespace std;

vector<int> b;
vector<int> c;

int main()
{
    int a[4005][5],n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=4;j++)
           scanf("%d",&a[i][j]);
    int k=0;
    for(int i=1;i<=n;i++)
    {   int p=a[i][1];
        for(int j=1;j<=n;j++)
        {   b.push_back(p+a[j][2]);
            k++;
        }
    }
    k=0;
    for(int i=1;i<=n;i++)
    {   int p=a[i][3];
        for(int j=1;j<=n;j++)
        {   c.push_back(p+a[j][4]);
            k++;
        }
    }
    sort(b.begin(),b.end());
    int cnt=0;
    for(int j=0;j<k;j++)
       if(find(b.begin(),b.end(),-c[j])!=b.end() )
           cnt=cnt+count(b.begin(),b.end(),-c[j]) ;


    printf("%d\n",cnt);
    return 0;
 }

Aucun commentaire:

Enregistrer un commentaire