Samkit5025

Untitled

Sep 22nd, 2022
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int totalBestSequences(int N, vector<int> &C){
  5.  
  6.     vector<int> pref(N+1,0);
  7.     for(int i=1;i<=N;i++)
  8.     {
  9.         pref[i] = pref[i-1] + C[i-1];
  10.     }
  11.  
  12.     map<int,int> hm;
  13.  
  14.     for(int i=0;i<=N;i++)
  15.     {
  16.         hm[pref[i]-i]++;
  17.     }
  18.  
  19.     int res =0;
  20.     for(auto i : hm){
  21.         res+=((i.second*i.second-i.second)/2);
  22.     }
  23.  
  24.     return res;
  25. }
  26.  
  27.  
  28. signed main() {
  29.    
  30.     int N;
  31.     cin>>N;
  32.    
  33.     vector<int> C(N);
  34.     for(int i=0;i<N;i++){
  35.         cin>>C[i];
  36.     }
  37.  
  38.     cout<<totalBestSequences(N,C)<<endl;
  39. }
  40.  
Advertisement
Add Comment
Please, Sign In to add comment