# Problem C- Eugene and an array | Codeforces Round 632 (Div 2)

Hello. I was trying to solve Problem C, and used the following approach.
Using dynamic programming,
for all dp(i, j) such that i, j >= 1
if dp(i, j-1) = 0 || dp(i+1, j) = 0 || sum from index i to j = 0, then dp(i, j) = 0
else dp(i, j) = 1

This is my solution, but it is giving me MLE for pretest 3.
-> https://codeforces.com/contest/1333/submission/75941303

I then changed the 2-dim array dp[][] to 1-dim and used this approach.
dp[i] = 0, if dp[i-1] = 0 or d[i] = 0, or sum from i to j = 0

Again I was getting correct output for all my testcases, but pretest 3 is giving me TLE
This is my solution using this approach.
-> https://codeforces.com/contest/1333/submission/75942879

The problem is that in pretest 3, the value of N = 2 x 10^5. Please help.

Number of subarrays with 0 sum is a common problem, and has a simple O(N) (O(NlogN) worst case) solution. Here’s the basic idea:

This question is a lot different then total subarrays with 0 sum.

What i did was i calculated ans like how many subarrays ending at ith index have a subsegment with sum=0,so all those for each index i-I calculated the largest index j(j<=i) such that sum(j,i)=0,so we cant include the subarrays with starting point <=j ,if there is no subarrys ending at ith position having sum=0,then we just add the maximum value of starting index occured previously because
since we have calculated ans for subarrays ending at [1,i-1] if for current index i we cant include those with starting index<=max starting index uptil now so just add ans+=(max starting index uptil now),if(there is a subarray ending at ith position having sum 0 and starting at pos=j){
if(max starting index<j)ans+=j,max starting index=j;
else ans+=max starting index
}
and finally ans=n*(n+1)/2 - ans
my solution :https://codeforces.com/contest/1333/submission/75895071

I used sub array approach only using maps. This is my code, see if you can find where you went wrong.

Code
``````	map<ll,ll> m;
ll s = 0,ans=0,n;
cin >> n;
V<ll> a(n+1,0),dp(n+1,0);
loop(i,1,n+1)cin >> a[i];
m = 1;
for(int i = 1 ; i <= n; ++i){
s+=a[i];
dp[i] = dp[i-1];
if(m.find(s) != m.end())dp[i] = max(dp[i],m[s]);
m[s] = i+1;
ans+=(i-dp[i]);
}
cout << ans << "\n"

``````
2 Likes

Hey can you comment the purpose of variables used in your code so that it becomes more clearer to understand. Thanks

1 Like