algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }