I was just trying to solve 1985C - Good Prefixes using C++ and this is my code, i dont know why but this code doesnt work for specific testcases. Please help me find the mistake.
My code:
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, c = 0;
cin >> n;
vector<long long int> v(n), s(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
if (i == 0) s[i] = v[i];
else s[i] = s[i - 1] + v[i];
}
for (int i = 1; i < n; i++) if (find(v.begin(), v.begin() + i + 1, s[i] / 2) != v.end() && s[i] % 2 == 0) c++;
if (v[0] == 0) c++;
cout << c << endl;
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
What about your s(n)? doesn't it still empty? U just filled up the vector v(n), but s(n) is still empty logically, mb this is the problem
Is it TLE ? find vector works for O(n) and time complexity of your code approximately n^2
Actually solution is easier
Hint: that element will be always max element in the prefix
Yes I used that method too, it got TLE, I just wanted to know what is wrong with my initial code, also, it wasn't TLE, it was WA
What do you mean by initial code, I have checked your submissions all got TL in test 3 because you wrote double for