Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int main() {
- int a;
- cin>>a;
- int pref[a+1][2];
- string s;
- cin>>s;
- pref[0][0]=0;
- pref[0][1]=0;
- long long dp[2000010];
- for (int i=0;i<2000010;i++) dp[i]=0;
- dp[1000000]=1;
- for (int i=1;i<=a;i++) {
- pref[i][0]=pref[i-1][0]; pref[i][1]=pref[i-1][1];
- if (s[i-1]=='a') pref[i][0]++; else pref[i][1]++;
- dp[1000000+pref[i][0]-pref[i][1]]++;
- }
- long long ans=0;
- for (int i=0;i<2000010;i++) ans+=(dp[i]*(dp[i]-1))/2;
- cout<<ans;
- // for (int i=999995;i<1000005;i++) cout<<dp[i]<<" ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement