 # FASTFOOD APRIL LUNCHTIME 2019

I have implemented a O(n) solution of the given problem code FASTFOOD which is giving the correct output but gets a TLE im subtask 2.I am curious to know the reason for the TLE in my code : https://www.codechef.com/viewsolution/24107986

``````for(i=0;i<N;i++)
{
cin>>B[i];
C[i]=A[i]-B[i];
D[i]=accumulate(C.begin(),C.begin()+1+i,0);
}
``````

You sure its O(N)??

### Complexity of Accumulate:

Linear in the distance between first and last.

2 Likes

You have used `accumulate` which is `O(n)`, so your code complexity becomes `O(n^2)`. Try to construct a partial sums from back of the array.

2 Likes

You are using std::accumulate…

``````            for(i=0;i<N;i++){
...
...
D[i]=accumulate(C.begin(),C.begin()+1+i,0);
}
``````

this is equivalent to

``````for(int i = 0; i < n ; i++){
for(j = 0; j <= i ; j++){
....
}
}``````
1 Like
``````#include<bits/stdc++.h>
#include<vector>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--> 0)
{
long long n,l=0,c=0,i;
cin>>n;
long long a[n],b[n],j=0,z=0;
for(i=0;i<n;i++)
{
cin>>a[i];
l=l+a[i];
}
for(i=0;i<n;i++)
{
cin>>b[i];
c=c+b[i];
}
//	if(l>c)
//	cout<<l<<"\n";
//	else
//	{

for(i=0;i<n;i++)
{
if(a[i]>b[i])
{
z=z+a[i];
l-=a[i];
c-=b[i];
//cout<<l<<"if -\n";
if(i==n-1)
cout<<z<<"\n";
}
else
{
if(l>c)
{
z=z+a[i];
l-=a[i];
c-=b[i];
//	j=i+1;
}
else
{

//for(j=i;j<n;j++)

z=z+c;
j=i+1;
//	cout<<z<<" else -\n";

}
//cout<<"else out \n";
}
//	cout<<"value of i ="<<i<<endl;
if(j>i)
{
cout<<z<<"\n";
break;
}
}
//	}

}
return 0;
}
``````

What is the error in my code ?
can some one guide me

1
5
18 7 9 9 3
20 4 13 4 10

Try to run your code on this test case . Your Output is 51 instead it should be 53
18+7+9+9+10 = 53 . First 4 days in Chefland and last day in Chefabad . Hope this helps 