main.cpp (1675B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 using namespace std; 11 12 // good := array such that some element can be represented as the sum of all other elements 13 // sum of all other elements is 0 if there are no other elements 14 // a_1,a_2,...,a_n 15 // count number of good non-empty prefixes of a 16 17 // the question here is this: 18 // does the largest thus far = the sum of all other numbers 19 // since sum of others is what matters, doesn't have to be most recent 20 21 // at each step: 22 // if current > largest 23 // sum += former largest 24 // largest = current 25 // else 26 // sum += current 27 // always 28 // compare sum with largest 29 30 31 int main() { 32 33 int testCases, n; 34 ll current; 35 cin >> testCases; 36 37 for(int z = 0; z < testCases; ++z) { 38 cin >> n; 39 vector<ll> ls {}; 40 for(int i = 0; i < n; ++i) { 41 cin >> current; 42 ls.push_back(current); 43 } 44 45 // stop at this point bc no individual number can be that big 46 ll upperBound = 1000000000; 47 ll largest = -1; 48 ll sum = 0; 49 int res = 0; 50 51 for(int i = 0; i < ls.size(); ++i) { 52 if(ls[i] > largest) { 53 if(largest != -1) { 54 sum += largest; 55 } 56 largest = ls[i]; 57 } else { 58 sum += ls[i]; 59 } 60 if(sum == largest) { 61 res += 1; 62 } 63 if(sum > upperBound) { 64 break; 65 } 66 } 67 cout << res << endl; 68 } 69 }