#include <bits/stdc++.h> using namespace std; #define int long long void solve() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<array<int, 2>> sc; { vector<int> sums; int m = n * (n - 1) / 2; sums.reserve(m); for (int i = 0; i < n; i++) { int s = 0; for (int j = i; j < n; j++) { s += a[j]; sums.push_back(s); } } // for (int v : sums) cerr << v << ' '; cerr << endl; sort(sums.begin(), sums.end()); // for (int v : sums) cerr << v << ' '; cerr << endl; int prev = sums[0]; int cnt = 0; for (int v : sums) { if (v == prev) cnt++; else { sc.push_back({prev, cnt}); prev = v; cnt = 1; } } sc.push_back({prev, cnt}); } int m = size(sc); int res = 0; for (int b = 0; b < m; b++) { int target = -sc[b][0]; if (!target) { if (sc[b][1] > 2) res += sc[b][1] * (sc[b][1] - 1) * (sc[b][1] - 2) / 6; // cerr << sc[b][0] << ' ' << sc[b][0] << ' ' << sc[b][0] << ' ' << sc[b][1] * (sc[b][1] - 1) * (sc[b][1] - 2) / 6 << endl; continue; } int l = b + 1; int r = m - 1; while (l <= r) { if (target == 2 * sc[l][0]) { res += sc[b][1] * sc[l][1] * (sc[l][1] - 1) / 2; // cerr << sc[b][0] << ' ' << sc[l][0] << ' ' << sc[l][0] << ' ' << sc[b][1] * sc[l][1] * (sc[l][1] - 1) / 2 << endl; l++; continue; } if (target == 2 * sc[r][0]) { res += sc[b][1] * sc[r][1] * (sc[r][1] - 1) / 2; // cerr << sc[b][0] << ' ' << sc[r][0] << ' ' << sc[r][0] << ' ' << sc[b][1] * sc[r][1] * (sc[r][1] - 1) / 2 << endl; r--; continue; } if (l == r) break; int s = sc[l][0] + sc[r][0]; if (s == target) { res += sc[b][1] * sc[l][1] * sc[r][1]; // cerr << sc[b][0] << ' ' << sc[l][0] << ' ' << sc[r][0] << ' ' << sc[b][1] * sc[l][1] * sc[r][1] << endl; l++; r--; } else if (s < target) { l++; } else { r--; } } if (sc[b][1] == 1) continue; target = -2 * sc[b][0]; for (l = b + 1; l < m; l++) { if (target == sc[l][0]) { res += sc[b][1] * (sc[b][1] - 1) / 2 * sc[l][1]; // cerr << sc[b][0] << ' ' << sc[b][0] << ' ' << sc[l][0] << ' ' << sc[b][1] * (sc[b][1] - 1) / 2 * sc[l][1] << endl; break; } } } cout << res << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); // #ifdef LOCAL // int t; cin >> t; while (t--) // #endif solve(); cout.flush(); }
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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <bits/stdc++.h> using namespace std; #define int long long void solve() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<array<int, 2>> sc; { vector<int> sums; int m = n * (n - 1) / 2; sums.reserve(m); for (int i = 0; i < n; i++) { int s = 0; for (int j = i; j < n; j++) { s += a[j]; sums.push_back(s); } } // for (int v : sums) cerr << v << ' '; cerr << endl; sort(sums.begin(), sums.end()); // for (int v : sums) cerr << v << ' '; cerr << endl; int prev = sums[0]; int cnt = 0; for (int v : sums) { if (v == prev) cnt++; else { sc.push_back({prev, cnt}); prev = v; cnt = 1; } } sc.push_back({prev, cnt}); } int m = size(sc); int res = 0; for (int b = 0; b < m; b++) { int target = -sc[b][0]; if (!target) { if (sc[b][1] > 2) res += sc[b][1] * (sc[b][1] - 1) * (sc[b][1] - 2) / 6; // cerr << sc[b][0] << ' ' << sc[b][0] << ' ' << sc[b][0] << ' ' << sc[b][1] * (sc[b][1] - 1) * (sc[b][1] - 2) / 6 << endl; continue; } int l = b + 1; int r = m - 1; while (l <= r) { if (target == 2 * sc[l][0]) { res += sc[b][1] * sc[l][1] * (sc[l][1] - 1) / 2; // cerr << sc[b][0] << ' ' << sc[l][0] << ' ' << sc[l][0] << ' ' << sc[b][1] * sc[l][1] * (sc[l][1] - 1) / 2 << endl; l++; continue; } if (target == 2 * sc[r][0]) { res += sc[b][1] * sc[r][1] * (sc[r][1] - 1) / 2; // cerr << sc[b][0] << ' ' << sc[r][0] << ' ' << sc[r][0] << ' ' << sc[b][1] * sc[r][1] * (sc[r][1] - 1) / 2 << endl; r--; continue; } if (l == r) break; int s = sc[l][0] + sc[r][0]; if (s == target) { res += sc[b][1] * sc[l][1] * sc[r][1]; // cerr << sc[b][0] << ' ' << sc[l][0] << ' ' << sc[r][0] << ' ' << sc[b][1] * sc[l][1] * sc[r][1] << endl; l++; r--; } else if (s < target) { l++; } else { r--; } } if (sc[b][1] == 1) continue; target = -2 * sc[b][0]; for (l = b + 1; l < m; l++) { if (target == sc[l][0]) { res += sc[b][1] * (sc[b][1] - 1) / 2 * sc[l][1]; // cerr << sc[b][0] << ' ' << sc[b][0] << ' ' << sc[l][0] << ' ' << sc[b][1] * (sc[b][1] - 1) / 2 * sc[l][1] << endl; break; } } } cout << res << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); // #ifdef LOCAL // int t; cin >> t; while (t--) // #endif solve(); cout.flush(); } |