#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> V(n), P{0}; for (int &x : V) { cin >> x; P.push_back(P.back() + x); } vector<int> VV; VV.reserve(n*(n+1)/2); for (int i=0; i<n; i++) for (int j=i; j<n; j++) VV.push_back(P[j+1]-P[i]); sort(VV.begin(), VV.end()); /* cerr << "VVsize = " << VV.size() << endl; */ long long result = 0; for (int i=0; i<(int)VV.size(); i++) { int itL = i+1; int itR = (int)VV.size()-1; int cntL=1, cntR=1; while (itL < itR) { /* cerr << "i=" << i << " itL=" << itL << " itR=" << itR << endl; */ if (VV[itL+1]==VV[itL]) { cntL++; itL++; continue; } if (VV[itR-1]==VV[itR]) { cntR++; itR--; continue; } int sum = VV[i] + VV[itL] + VV[itR]; if (sum==0) { result += (long long)cntL*cntR; itL++; itR--; cntL = cntR = 1; } else if (sum < 0) { itL++; cntL = 1; } else { itR--; cntR = 1; } } if (itR>i && itL<(int)VV.size() && VV[itL]==VV[itR] && (VV[i]+VV[itL]+VV[itR]==0)) result += (cntL + cntR - 1) * (cntL + cntR - 2) / 2; } cout << result << '\n'; return 0; }
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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> V(n), P{0}; for (int &x : V) { cin >> x; P.push_back(P.back() + x); } vector<int> VV; VV.reserve(n*(n+1)/2); for (int i=0; i<n; i++) for (int j=i; j<n; j++) VV.push_back(P[j+1]-P[i]); sort(VV.begin(), VV.end()); /* cerr << "VVsize = " << VV.size() << endl; */ long long result = 0; for (int i=0; i<(int)VV.size(); i++) { int itL = i+1; int itR = (int)VV.size()-1; int cntL=1, cntR=1; while (itL < itR) { /* cerr << "i=" << i << " itL=" << itL << " itR=" << itR << endl; */ if (VV[itL+1]==VV[itL]) { cntL++; itL++; continue; } if (VV[itR-1]==VV[itR]) { cntR++; itR--; continue; } int sum = VV[i] + VV[itL] + VV[itR]; if (sum==0) { result += (long long)cntL*cntR; itL++; itR--; cntL = cntR = 1; } else if (sum < 0) { itL++; cntL = 1; } else { itR--; cntR = 1; } } if (itR>i && itL<(int)VV.size() && VV[itL]==VV[itR] && (VV[i]+VV[itL]+VV[itR]==0)) result += (cntL + cntR - 1) * (cntL + cntR - 2) / 2; } cout << result << '\n'; return 0; } |