#include<bits/stdc++.h> using namespace std; vector <long long> RAWInput, Input; map <long long, long long> Neighbourhood[500*500+21]; int main() { int n; cin >> n; int x; for (int j = 0; j < n; ++j) { cin >> x; RAWInput.push_back(x); } for (int i = 0; i < n; ++i) { long long tempsum = RAWInput[i]; Input.push_back(tempsum); for (int j = i + 1; j < n; ++j) { tempsum += RAWInput[j]; Input.push_back(tempsum); } } for (int i = 0; i < Input.size(); ++i) { for (int j = i+1; j < Input.size(); ++j) { ++Neighbourhood[i][Input[j]]; } } long long answer = 0; for (int i = 0; i < Input.size(); ++i) { long long tempsum = Input[i]; for (int j = i+1; j < Input.size(); ++j) { tempsum += Input[j]; if (Neighbourhood[j][-tempsum]) answer += Neighbourhood[j][-tempsum]; tempsum -= Input[j]; } } cout << answer << "\n"; }
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 | #include<bits/stdc++.h> using namespace std; vector <long long> RAWInput, Input; map <long long, long long> Neighbourhood[500*500+21]; int main() { int n; cin >> n; int x; for (int j = 0; j < n; ++j) { cin >> x; RAWInput.push_back(x); } for (int i = 0; i < n; ++i) { long long tempsum = RAWInput[i]; Input.push_back(tempsum); for (int j = i + 1; j < n; ++j) { tempsum += RAWInput[j]; Input.push_back(tempsum); } } for (int i = 0; i < Input.size(); ++i) { for (int j = i+1; j < Input.size(); ++j) { ++Neighbourhood[i][Input[j]]; } } long long answer = 0; for (int i = 0; i < Input.size(); ++i) { long long tempsum = Input[i]; for (int j = i+1; j < Input.size(); ++j) { tempsum += Input[j]; if (Neighbourhood[j][-tempsum]) answer += Neighbourhood[j][-tempsum]; tempsum -= Input[j]; } } cout << answer << "\n"; } |