#include <iostream> #include <string> #include <algorithm> #include <vector> #include <unordered_map> #define LL long long #define PI pair<int, int> using namespace std; constexpr int M = 10000000; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> arr(n); unordered_map<int, int> cnt; vector<PI> S; for (int i = 0; i < n; ++i) cin >> arr[i]; for (int i = 0; i < n; ++i) { int s = 0; for (int j = i; j < n; ++j) { s += arr[j]; ++cnt[s]; } } LL res = 0ll; res += (LL) cnt[0] * (LL) (cnt[0] - 1ll) * (LL) (cnt[0] - 2ll) / 6ll; for (auto &[a, b] : cnt) { S.emplace_back(a, b); if (b > 1 && a && cnt.count(-2 * a)) { res += (LL) b * (LL) (b - 1) * (LL) cnt[-2 * b]; } } sort(S.begin(), S.end()); int m = (int) S.size(); for (int i = 0; i <= m - 2; ++i) { int j = i + 1; int k = m - 1; while (j < k) { if (S[i].first + S[j].first + S[k].first == 0) { res += (LL) S[i].second * (LL) S[j].second * (LL) S[k].second; ++j; --k; } else if (S[i].first + S[j].first + S[k].first > 0) --k; else ++j; } } cout << res; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <iostream> #include <string> #include <algorithm> #include <vector> #include <unordered_map> #define LL long long #define PI pair<int, int> using namespace std; constexpr int M = 10000000; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> arr(n); unordered_map<int, int> cnt; vector<PI> S; for (int i = 0; i < n; ++i) cin >> arr[i]; for (int i = 0; i < n; ++i) { int s = 0; for (int j = i; j < n; ++j) { s += arr[j]; ++cnt[s]; } } LL res = 0ll; res += (LL) cnt[0] * (LL) (cnt[0] - 1ll) * (LL) (cnt[0] - 2ll) / 6ll; for (auto &[a, b] : cnt) { S.emplace_back(a, b); if (b > 1 && a && cnt.count(-2 * a)) { res += (LL) b * (LL) (b - 1) * (LL) cnt[-2 * b]; } } sort(S.begin(), S.end()); int m = (int) S.size(); for (int i = 0; i <= m - 2; ++i) { int j = i + 1; int k = m - 1; while (j < k) { if (S[i].first + S[j].first + S[k].first == 0) { res += (LL) S[i].second * (LL) S[j].second * (LL) S[k].second; ++j; --k; } else if (S[i].first + S[j].first + S[k].first > 0) --k; else ++j; } } cout << res; } |