# Why is TLE in this codeforces problem? https://codeforces.com/contest/1352/problem/E

Approach - The frequency of all elements of the array is stored in a map. Then loop over all elements of the array, and on every step maintain a list of the sums of all subarrays ending at that position. This list of sums can be created by adding the current element to all existing sums, and afterwards adding the current element as a new sum to the list.

Example- for an array with elements [3,1,4…]. After third, before fourth step the list of sums will contain the elements [3+1+4,1+4,4].

So, on every loop we create an inner loop over the sums so far, and check using the frequency array how much elements with the sum exist, adding that number to ans. Set the frequency of an element to zero after having counted it once. Then it is counted as zero the next time.
My code-
#include <bits/stdc++.h>
using namespace std;
int count(int *v, int n, map<int,int>m)
{
int sum=0;
vectorlst;
lst.push_back(v);
for(int i=1;i<n;i++)
{
for(int j=0;j<lst.size();j++)
{
lst[j]=lst[j]+v[i];
if(m.find(lst[j])!=m.end())
sum=sum+m[lst[j]];
m[lst[j]]=0;
}
lst.push_back(v[i]);
}
delete [] v;
return sum;
}
int main()
{
std::ios::sync_with_stdio(false);
int t,n,e,c;
cin>>t;
while(t–)
{
cin>>n;
int *v=new int[n];
map<int,int>m;
c=0;
for(int i=0;i<n;i++)
{
cin>>v[i];
m[v[i]]=m[v[i]]+1;
}
c=count(v,n,m);
std::cout << c << std::endl;
}
return 0;
}

First, format code or just link your submission that TLE’s (better option)

Map is just slow in this problem, you probably aren’t intended to use it, especially when n = 8000. There are multiple better approaches.

1 Like

Yes, as galencolin said, maps are slow for this problem. i tried with maps but got TLE so i switched to frequency array of sums, changing the sum to 0 once i increment the answer. got an AC.

Check the editorial for the same approach but better explanation.

1 Like