Problem Info
Good subarrays: Problem - C - Codeforces
Question
My code is almost the same as the solution by Matthew chen but somehow mine is giving the wrong answer for test 3 (N= 100000, string = all 1s). I have no idea where I made a mistake.
My Work
#include <bits/stdc++.h>
using namespace std;
int main() {
size_t T; cin >> T;
for (size_t i=0; i<T; ++i){
size_t N; cin >> N;
ssize_t prefix = 0;
map<ssize_t, ssize_t> prefixes;
prefixes[0] = 1;
size_t count = 0;
for (size_t j=0; j<N; ++j){
char dig; cin >> dig;
dig -= '1';
prefix = prefix + dig;
count += prefixes[prefix];
++prefixes[prefix];
}
cout << count << "\n";
}
}
The solution code is :
// key idea is the following: we subtract one from each element of a[n] to form a new array b[n]
// If a subarray is good in the original array a, then since its sum is equal to its length,
// the subarray is now good if its sum is 0 in b.
#include <bits/stdc++.h>
using namespace std;
int main() {
const int MN = 1e5+10;
int n, t, a[MN];
char x;
cin >> t;
for (int i=0; i<t; i++) {
cin >> n;
for (int k=0; k<n; k++) {
cin >> x;
a[k] = x-'1';
}
map<int, int> sums;
sums[0] = 1;
long long psum = 0, answer = 0;
for (int j=0; j<n; j++) {
psum+=a[j];
answer += sums[psum];
sums[psum]++;
}
cout << answer << endl;
memset(a, 0, n+1), sums.clear();
}
}