Advertisement
Guest User

Untitled

a guest
Oct 16th, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6. int a;
  7. cin>>a;
  8.  
  9.  
  10. int pref[a+1][2];
  11. string s;
  12. cin>>s;
  13. pref[0][0]=0;
  14. pref[0][1]=0;
  15.  
  16. long long dp[2000010];
  17.  
  18. for (int i=0;i<2000010;i++) dp[i]=0;
  19. dp[1000000]=1;
  20. for (int i=1;i<=a;i++) {
  21. pref[i][0]=pref[i-1][0]; pref[i][1]=pref[i-1][1];
  22. if (s[i-1]=='a') pref[i][0]++; else pref[i][1]++;
  23. dp[1000000+pref[i][0]-pref[i][1]]++;
  24. }
  25. long long ans=0;
  26. for (int i=0;i<2000010;i++) ans+=(dp[i]*(dp[i]-1))/2;
  27. cout<<ans;
  28. // for (int i=999995;i<1000005;i++) cout<<dp[i]<<" ";
  29. return 0;
  30. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement