Submission #3791209

---

Source Code Expand

#include <bits/stdc++.h> 

#define INF INT_MAX/2
#define MOD 1000000007

using namespace std;

using ll = long long;
using ull = unsigned long long;

ll nCr(ll n,ll r){
   if(r == 0) return 1;
   if(r == n) return 1;
   if(r == 1) return n;
   if(n < r) return 0;
   return nCr(n-1,r-1)+nCr(n-1,r);
}

int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);

   int N;
   cin>>N;
   vector<ll>A(N);
   for(int i=0;i<N;i++)cin>>A[i];
   vector<ll>sum(N);
   sum[0]=A[0];
   for(int i=1;i<N;i++){
      sum[i] += sum[i-1]+A[i];
   }
   sort(sum.begin(),sum.end());
   ll ans = 0;

   for(int i=0;i<N;i++){
      int num = 1;
      while(i<N&&sum[i]==sum[i+1]){
         num++;
         i++;
      }

      if(num == 1)continue;
      else ans += nCr(num,2);
   }

   for(int i=0;i<N;i++)if(sum[i]==0)ans++;

   cout<<ans<<endl;
   return 0;
}

Submission Info

Judge Result